給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

想法：感覺這個題考的是數學，是邏輯。
怎麼找矩形呢？就是當前位置的最高點，向左和向右畫矩形，找他比他矮的點left, right，就停止。
高度就是height[i]
寬度就是(right-left+1)-2，因為找到的那兩個點是不能算進去的，所以要-2，理解這個-2，後面的優化算法也就好理解了。

一、暴力枚舉
我在暴力枚舉的時候，向左向右找的點，是>=自己高度的最後一個點，所以是right-left+1。

    public int largestRectangleArea2(int[] heights) {
        int n = heights.length;
        int max = 0;
        int last = -1;
        for (int i = 0; i < n; i++) {
            int h = heights[i];
            // 剪枝操作，這一步讓測試通過了
            if (h == last) {
                continue;
            }
            int left = -1;
            int right = -1;
            // to right
            for (int j = i + 1; j < n; j++) {
                if (heights[j] < h) {
                    right = j - 1;
                    break;
                }
            }
            if (right == -1) {
                right = n - 1;
            }
            for (int j = i - 1; j >= 0; j--) {
                if (heights[j] < h) {
                    left = j + 1;
                    break;
                }
            }
            if (left == -1) {
                left = 0;
            }
            max = Math.max((right - left + 1) * h, max);
            last = h;
        }
        return max;
    }

二、優化算法
難點就在於怎麼找兩邊的那兩個點。因為每個點都是不同高度的，我的思維就限在了，怎麼去區分不同的高度上。實際上不用關心具體的高度，只用關心高度是上升還是下降的。記住拐點。

哨兵+棧
一頭一尾插入哨兵
過程中怎麼找矩形呢？

• 遍歷開始

  • 把“我” 和 棧頂元素比，一旦我比棧頂元素a矮，那棧頂元素的矩形面積就到頭了（因為它不能再延伸了），則進入循環
  • pop棧頂元素a
  • 其面積由它向兩邊延伸的第一個矮點確定，兩邊第一個矮點分別是我和下一個棧頂元素
  • 寬度 = ( 我 - 下一個棧頂元素b + 1 ) - 2
  • 循環直到我>=棧頂元素可跳出循環
• push我
• 遍歷結束

1、ArrayDeque存儲

    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int n = heights.length + 2;
        int[] newHeights = new int[n];
        System.arraycopy(heights, 0, newHeights, 1, n - 2);
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (int i = 1; i < n; i++) {
            int h = heights[i];
            while (h < heights[stack.peek()]) { // 發現了拐點（確定了兩個矮點），進入循環
                int confirmIdx = stack.pop(); // 該位置最大矩形已確認
                max = Math.max(max, heights[confirmIdx] * (i - stack.peek() - 1)); // 即兩個矮點的距離-2
            }
            stack.push(i);
        }
        return max;
    }

2、int[]手搓一個棧

    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int n = heights.length + 2;
        int[] newHeights = new int[n];
        System.arraycopy(heights, 0, newHeights, 1, n - 2);
        heights = newHeights;

        int[] stack = new int[heights.length];
        int top = 0;
        stack[0] = 0;
        for (int i = 1; i < n; i++) {
            int h = heights[i];
            while (h < heights[stack[top]]) {
                int confirmIdx = stack[top--];
                max = Math.max(max, heights[confirmIdx] * (i - stack[top] - 1));
            }
            stack[++top] = i;
        }
        return max;
    }