84 Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

class Solution {
    // 对于每个index，知道它最多能保持自己高度往左右扩散多远就是这个位置能得到的最大面积
    // 用单调栈的时候关注两个问题，栈内是什么，以及出栈的条件是什么
    // 同时要注意一个隐藏性质: 不在栈内但是紧邻栈头的元素一定是大于(如果是单调增)当前栈头的
    // 对于本题，栈内是最大面积还不能确定的index，出栈条件是往右扩散的最大距离确定时，
    // 也就是遇到了比当前高度低的bar
    // *往左扩散的距离是确定的，由于栈内元素是递增的，在自己和上个栈元素之间的idx没有在栈里
    // 这表明他们都大于当前的元素，因此他们都是可以被扩散到的*
    // 对于第一个和最后一个元素，由于他们会没有上个/下个元素，因此两边加上0作为dummy边界
    
    // 注意这道题保存坐标而不是高度的做法
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] arr = new int[n + 2];
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        arr[0] = 0;
        arr[n + 1] = 0;
        for (int i = 0; i < n; i++) {
            arr[i+1] = heights[i];
        }
        stack.push(0);
        for (int i = 1; i <= n+1; i++) {
            int hei = arr[i];
            if (arr[stack.peek()] < hei) {
                stack.push(i);
            } else {
                while (arr[stack.peek()] > hei) {
                    int curidx = stack.pop();
                    int curhei = arr[curidx];
                    ans = Math.max(ans, curhei*(i - stack.peek() - 1));
                }
                // 仍然需要push这个index
                stack.push(i);
            }
        }
        return ans;
    }
}