84 Largest Rectangle in Histogram

Leetcode

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

---

使用一个单调递增栈来储存单调递增高度的 index ，如果遇到下一个矩形的高度比栈顶小，则把比这个栈顶高的 index 都 pop 出来，并计算 pop 出的矩形的高度和面积。根据当前矩形的位置和栈顶元素可知弹出的这个矩形的最大宽度，所以可以算出面积。

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack=new LinkedList<>();
    int max=0;
    for(int i=0;i<=heights.length;++i){
        int h=i==heights.length?-1:heights[i];
        while(!stack.isEmpty() && heights[stack.peek()]>h){
            int height=heights[stack.pop()];
            int width=stack.isEmpty()? i:i-stack.peek()-1;
            int area=width*height;
            if(area>max) max=area;
        }
        stack.push(i);
    }
    return max;
}