84 Largest Rectangle in Histogram

84. Largest Rectangle in Histogram

1. Question

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area =10unit.

For example, Given heights =[2,1,5,6,2,3], return10.

2. Implementation

思路: 矩形的面积决定于宽和高，高度越高，面积可能越大，基于这样的思想，我们可以利用单调递增栈，存储有着单调递增高度的 数组index，当栈顶所存的index所对应的高度大于等于当前高度时，我们才开始计算可以得到的矩形面积。注意一个极端的情况是所给的输入高度是单调递增的，为了让stack出栈，我们在遍历输入数组时，会遍历到i等于heights.length, 并且设置curHeight为-1，因为高度一定是非负，这样就可以保证stack存储的内容最后一定会出栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0, area = 0, curHeight = 0;

        for (int i = 0; i <= heights.length; i++) {
            curHeight = i == heights.length ? -1 : heights[i];

            while (!stack.isEmpty() && heights[stack.peek()] >= curHeight) {
                int index = stack.pop();
                area = heights[index] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, area);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

3. Time & Space Complexity

时间和空间都是O(n)