Java practice on stack based solution


  • 0
    D
    public class Solution {
        class Tile {
            int width;
            int height;
            Tile(int width, int height) {
                this.width = width;
                this.height = height;
            }
        }
        
        private int area;
        private Stack<Tile> stack = new Stack<>();
        
        private int shrinkStack(int height) {
            int width = 0;
            while (stack.size() > 0 && stack.peek().height >= height) {
                area = Math.max(area, (stack.peek().width + width) * stack.peek().height);
                width += stack.peek().width;
                stack.pop();
            }
            return width;
        }
        
        public int largestRectangleArea(int[] heights) {
            if (heights == null || heights.length == 0) {
                return 0;
            }
            for (int height : heights) {
                stack.push(new Tile(shrinkStack(height) + 1, height));
            }
            shrinkStack(0);
            return area;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.