public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) return 0;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < heights.length; i++) {
        //往左找，往右找
        int left = i, right = i;
        while (left >= 0 && heights[left] >= heights[i]) left--;
        while (right < heights.length && heights[right] >= heights[i]) right++;
        max = Math.max(max, heights[i] * (right - left - 1));
    }
    return max;
}

/**
 * 单调栈，思路：
 * 栈中存的是下标，代表了矩形宽度的起点start,i代表end位置，heights[i]代表了当前柱状图的高度，heights[stack.peek]就代表栈顶高度
 * 低高（12）类型，入栈：因此栈顶的值就是：以栈顶柱状图高度（heights[stack.peek]）为矩形的起点start
 * 高低（21）类型，出栈：遇到比栈顶对应的高度小的（heights[i] < heights[stack.peek]），说明以heights[stack.peek]为高的矩形被确定，宽度为i - stack.peek() - 1
 * 循环上述出栈过程直到满足12类型，每次出栈对比累计最大值和当前矩形最大值
 * 哨兵的添加：最后栈中剩下的满足12类型，为了方便继续比较，则增加末尾哨兵为0变成120，于是遍历到0的时候20满足了21类型，2出栈，10也满足21类型，结束。
 */
public class eight_four_柱状图中的最大矩形_other {

    @Test
    public void test(){
        int[] heights = {2, 1, 5, 6, 2, 3};
        int res = largestRectangleArea(heights);
        System.out.println(res);
    }

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) return 0;
        if (len == 1) return heights[0];

        int res = 0;
        int[] newHeights = new int[len + 2];
        newHeights[0] = 0;
        System.arraycopy(heights, 0, newHeights, 1, len);
        newHeights[len + 1] = 0;
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>(len);
        // 先放入哨兵，在循环里就不用做非空判断
        stack.addLast(0);

        for (int i = 1; i < len; i++) {
            while (heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return res;
    }
}