技巧：使用哨兵（sentienel），避免特殊情况的讨论，比如单链表虚拟头结点、插入排序等。

暴力破解

先确定高度，再确定宽度：循环遍历数组，即先确定高度，再向左、右确定每个序号的左、右边界，即宽度 width，那么面积 area = width * length。

// 暴力法
public int largestRectangleArea2(int[] heights) {
    if (heights.length == 0) return 0;
    int left, right;
    int maxArea = Integer.MIN_VALUE;
    for (int i = 0; i < heights.length; i++) {
        // 确定左指针
        left = i;
        right = i;
        while (left > 0 && heights[left - 1] >= heights[i]) {
            left--;
        }
        // 确定右指针
        while (right < heights.length -1 && heights[right + 1] >= heights[i]) {
            right++;
        }
        // 计算面积
        int a = (right - left + 1) * heights[i];
        maxArea = Math.max(maxArea, a);
    }
    return maxArea;
}

单调栈

使用一个栈保持元素

public int largestRectangleArea(int[] heights) {
    if (heights.length == 0) return 0;
    int maxArea = Integer.MIN_VALUE;
    int len = heights.length;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < len; i++) {
        // 出栈操作
        while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
            // 栈顶>外部元素，证明找到栈顶的右边界
            int height = heights[stack.pop()];
            int width;
            if (stack.isEmpty()) {
                width = i; // 注意
            } else {
                width = i - stack.peek() - 1;
            }
            maxArea = Math.max(maxArea, width * height);
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int height = heights[stack.pop()];
        int width;
        if (stack.isEmpty()) {
            width = len; // 注意
        } else {
            width = len - stack.peek() - 1;
        }
        maxArea = Math.max(maxArea, width * height);
    }
    return maxArea;
}

优化：单调栈+哨兵（sentinel）

以上参考代码 2 需要考虑两种特殊的情况：
弹栈的时候，栈为空；
遍历完成以后，栈中还有元素；
为此可以我们可以在输入数组的两端加上两个高度为 0 （或者是 0.5，只要比 1 严格小都行）的柱形，可以回避上面这两种分类讨论。
这两个站在两边的柱形有一个很形象的名词，叫做哨兵（Sentinel）。
有两个柱形：

1. 左边的柱形（第 1 个柱形）由于它一定比输入数组里任何一个元素小，它肯定不会出栈，因此栈一定不会为空；

2. 右边的柱形（第 2 个柱形）也正是因为它一定比输入数组里任何一个元素小，它会让所有输入数组里的元素出栈（第 1 个哨兵元素除外）。 ```java public int largestRectangleArea(int[] heights) { if (heights.length == 0) return 0; int area = 0; int len = heights.length + 2; // 增加两个哨兵 int[] newHeights = new int[len]; newHeights[0] = 0; newHeights[len-1] = 0; System.arraycopy(heights, 0, newHeights, 1, len-2);

   Deque stack = new ArrayDeque<>(); stack.addLast(0); // 放入哨兵0 for (int i = 1; i < len; i++) {

    // 满足条件进行出栈计算：栈顶元素>外部元素
    int height, width;
    while (newHeights[stack.peekLast()] > newHeights[i]) {
        height = newHeights[stack.pollLast()];
        width = i - stack.peekLast() - 1;
        area = Math.max(area, height * width);
    }
    stack.addLast(i); // 入栈

   }

   return area;

} ```

单调栈练习