[Vssue]0084.柱状图中最大的矩形.md

[youngyangyang04]

https://www.programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html

[heimenkyou]

像java这种传参是普通数组的在前后加0就不太方便了, 可以通过一些小小的判断来代替加0:

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 单调栈
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        for (int i = 0; i <= heights.length; i++) {
            // 末尾加一个0, 方便计算
            int cur = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && cur < heights[stack.peek()]) {
                int top = stack.pop();
                // 左边第一个比当前小的
                int left = stack.isEmpty() ? -1 : stack.peek(); // 开头加一个0
                // 右边第一个比当前小的
                int right = i;
                // 宽度
                int width = right - left - 1;
                // 高度
                int height = heights[top];
                // 计算面积
                res = Math.max(res, width * height);
            }
            stack.push(i);
        }
        return res;
    }
}