Leetcode--Java--84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

单调栈

暴力思路：左边找一个比当前位置高度小的，右边找个比当前位置高度小的，则以当前位置向两边拓展能达到的最大面积为，

如果直接暴力枚举所有点，再分别枚举向左边和向右边拓展，会超时维护一个单调递增的栈，只要比栈顶大就入栈，比栈顶小，此时以栈顶前一个，栈顶，和当前元素就符合了计算cur位置的最大面积条件。 例如栈里5， 6，来了一个2小技巧。考虑到首尾也可能算入面积计算，为了避免复杂的边界处理，这里给首尾设置两个哨兵0

相似题目：接雨水

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int newheight[] = new int[n + 2];
        for (int i = 1; i <= n; i ++ ) {
            newheight[i] = heights[i - 1];
        }
        int res = 0;
        Deque stack = new ArrayDeque<>();
        for (int i = 0; i < n + 2; i ++ ) {
            //如果当前值比栈顶小，就构成了一组可计算面积的
            while (!stack.isEmpty() && newheight[i] < newheight[stack.peek()]) {
                int cur = stack.pop();
                res = Math.max(res, (i - stack.peek() - 1) * newheight[cur]);
            }
            //比栈顶大，就入栈，维护单调递增栈
            stack.push(i);
        }
        return res;
    }
}