# 0084. Largest Rectangle in Histogram
###### tags: `Leetcode` `Hard` `Stack`
Link: https://leetcode.com/problems/largest-rectangle-in-histogram/
## 思路
参考[这里](https://abhinandandubey.github.io/posts/2019/12/15/Largest-Rectangle-In-Histogram.html)
**遇到算rectangle的问题就想怎么才能在一个数pop的时候把以它为高的rectangle全算出来**
每次如果一个新的bar来了，并且比现在 栈顶元素对应的heights(h)小，就说明之后产生的rectangle高度不可能再到达h了，此时说明h应该被pop掉，并且记录一下这个bar带来的rectangle area，也就是用它的```height*(i-stack.isEmpty()?0:(stack.peek()+1))```
要注意的是这里是找```stack.peek()+1```而不是用刚才pop出来的idx 因为从现在的peek到刚pop出来的index中间可能有比pop的高度更高的 但之前被pop出去了
最后返回最大的area
## Code

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < heights.length;i++){
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                int h = heights[stack.pop()];
                int w = i-(stack.isEmpty()?0:(stack.peek()+1));
                maxArea = Math.max(maxArea, h*w);
            }
            stack.push(i);
        }
        // finally pop out any bar left in the stack and calculate the area based on it
        while (!stack.isEmpty()) {
            maxArea = Math.max(maxArea, heights[stack.pop()] * (heights.length - (stack.isEmpty() ? 0 : stack.peek() + 1)));
        }
        return maxArea;
    }
}