Short and Clean O(n) stack based JAVA solution
For explanation, please see https://bit.ly/2we8Wfx\n\n\n    public int largestRectangleArea(int[] heights) {\n        int len = heights.length;\n        Stack<I
For explanation, please see https://bit.ly/2we8Wfx\n\n```\n    public int largestRectangleArea(int[] heights) {\n        int len = heights.length;\n        Stack<Integer> s = new Stack<>();\n        int maxArea = 0;\n        for (int i = 0; i <= len; i++){\n            int h = (i == len ? 0 : heights[i]);\n            if (s.isEmpty() || h >= heights[s.peek()]) {\n                s.push(i);\n            } else {\n                int tp = s.pop();\n                maxArea = Math.max(maxArea, heights[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));\n                i--;\n            }\n        }\n        return maxArea;\n    }\n```\n\nOP\'s Note: Two years later I need to interview again. I came to this problem and I couldn\'t understand this solution. After reading the explanation through the link above, I finally figured this out again. \nTwo key points that I found helpful while understanding the solution: \n\n1. When a bar is popped, we calculate the area with the popped bar at index ``tp`` as shortest bar. Now we know the rectangle **height** is ``heights[tp]``, we just need rectangle width to calculate the area.\n2. How to determine rectangle **width**? The maximum width we can have here would be made of all connecting bars with height greater than or equal to ``heights[tp]``. ``heights[s.peek() + 1] >= heights[tp]`` because the index on top of the stack right now ``s.peek()`` is the first index left of ``tp`` with height smaller than tp\'s height (if ``s.peek()`` was greater then it should have already been poped out of the stack). ``heights[i - 1] >= heights[tp]`` because index ``i`` is the first index right of ``tp`` with height smaller than tp\'s height (if ``i`` was greater then ``tp`` would have remained on the stack). Now we multiply height ``heights[tp]`` by width ``i - 1 - s.peek()`` to get the **area**.\n\n
['Java']