Descriptive and clean Java solution


  • 0
    R
    class Solution {
        
        // each object in stack contains height and width info
        class Data {
            public int height;
            public int width;
            public Data (int height, int width) {
                this.height = height;
                this.width = width;
            }
        }
        
        public int largestRectangleArea(int[] heights) {
            if(heights == null || heights.length == 0)
                return 0;
            Stack<Data> stack = new Stack<>();
            stack.push(new Data(heights[0], 1));
            
            int max = heights[0];
            for(int i = 1; i < heights.length; i++) {
                if(heights[i] >= stack.peek().height)
                    stack.push(new Data(heights[i], 1));
                else {
                    int width = 0;
                    while(!stack.empty() && stack.peek().height > heights[i]) {
                        Data data = stack.pop();
                        width = data.width + width;
                        int currentVal = data.height * (width);
                        max = Math.max(max, currentVal);
                    }
                    max = Math.max(max, (width + 1) * heights[i]);
                    stack.push(new Data(heights[i], width + 1));
                }
            }
            
        // now we have a histogram in ascending order
        // Start from right to left, find the max rectangle
            int width = 0;
            int height = 0;
            while(!stack.empty()) {
                Data data = stack.pop();
                height = data.height;
                width = data.width + width;
                int currentVal = data.height * (width);
                max = Math.max(max, currentVal);
            }
            
            return max;
        }
    }
    

Log in to reply
 

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