Leetcode 柱状图中最大的矩形

在这里插入图片描述

h 是右边界，连续多个高度递增的柱子，如果遇到下一个 h < 栈顶元素(是最大的元素，单调递增栈)，那么会不断出栈来更新计算最大面积。

并非是一次性计算出最大面积的，很重要的一点是while (!stack.isEmpty()这一部分的判断条件，会持续多次计算并更新最大面积，

你提到的情况是非常重要的，并且确实在某些情况下会让人觉得应该以栈底元素为高度，但实际上这需要从栈的完整处理流程来理解。我们仍然应该按照栈顶元素作为当前高度来计算矩形面积，而栈底元素最终也会被弹出并正确处理。

让我们详细分析这个具体输入 [5, 6, 7, 2] 的执行过程，看看为何最终仍会正确地处理到以栈底元素 5 为高度的矩形。

步骤解析：

初始化：

我们的输入数组是 [5, 6, 7, 2]，依然使用单调栈来计算最大矩形面积。
遍历每个柱子，同时维护一个递增栈（存放柱子的索引）。

遍历开始：

i = 0, heights[0] = 5：
- 栈为空，将 0 压入栈，栈为 [0]。
i = 1, heights[1] = 6：
- 栈顶元素对应的高度是 5，6 > 5，继续保持递增顺序，将 1 压入栈，栈为 [0, 1]。
i = 2, heights[2] = 7：
- 栈顶元素对应的高度是 6，7 > 6，继续递增，将 2 压入栈，栈为 [0, 1, 2]。
i = 3, heights[3] = 2：
- 现在，当前柱子 2 < 7，不再递增了，我们需要弹出栈顶来计算面积。

弹栈计算过程：

弹出 2 索引的柱子 (高度 7)：
- 栈顶的高度是 7，宽度为 1（因为 i - stack.peek() - 1 = 3 - 1 - 1 = 1），即矩形面积为 7 * 1 = 7。
- 更新最大面积为 7。
弹出 1 索引的柱子 (高度 6)：
- 栈顶的高度是 6，宽度为 2（因为 i - stack.peek() - 1 = 3 - 0 - 1 = 2），即矩形面积为 6 * 2 = 12。
- 更新最大面积为 12。
弹出 0 索引的柱子 (高度 5)：
- 栈顶的高度是 5，宽度为 3（因为栈已为空，所以宽度就是 i = 3），即矩形面积为 5 * 3 = 15。
- 更新最大面积为 15。

继续遍历：

压入当前柱子 2：
- 现在将索引 3 压入栈，栈为 [3]。

遍历结束：

遍历结束后，栈中还有元素 3，对应的高度是 2，我们需要处理剩余的栈：
- 以高度 2 作为最后的矩形，高度为 2，宽度为 4（因为栈为空，宽度就是整个数组的长度 n = 4），即矩形面积为 2 * 4 = 8。

最终结果：

最大面积是 15，对应的就是以高度 5 的矩形。

总结：

在 [5, 6, 7, 2] 的案例中，当遇到比栈顶更小的 2 时，栈中的元素会依次被弹出，首先以 7 作为高度计算矩形面积，接着以 6，最后以 5。栈底元素 5 也会在这个过程中被正确地弹出，并计算出它作为高度的最大矩形面积，因此最终以栈底元素 5 为高度的矩形仍然会被正确计算。
之所以使用栈顶元素作为 height，是因为栈顶元素对应的柱子是当前需要被“封闭”的柱子，当前柱子限制了栈顶柱子的右边界，所以我们需要计算以它为高度的最大矩形。
栈底元素最终也会被弹出并处理，只不过它的处理顺序是等到它的右边界被确定之后才会弹出计算，确保不会漏掉任何可能形成的更大矩形。

java solution

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        //栈中存放的是柱子的下标,而不是高度值
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i <= n; ++i) {
            //h是当前柱子的高度,当i == n 时意味着到达了我们设置的最右边界
            int h = (i == n) ? 0 : heights[i];
            //stack中的下标对应的元素值是递增的,栈顶元素作为下标所对应的元素是之前连续递增高度的最大值,
            //而h小于栈顶元素下标对应高度值,意味着碰到了右边界,需要我们持续出栈来多次更新计算最大面积值
            while(!stack.isEmpty() && h < heights[stack.peek()]) {
                //确定高度和宽度
                int height = heights[stack.pop()];
                int width = (stack.isEmpty()) ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

关于宽度的确定

int width = stack.isEmpty() ? i : i - stack.peek() - 1;

这行代码是用于计算当前弹出的栈顶元素形成的矩形的宽度。它看起来有点复杂，但其实逻辑很清楚：我们要确定以弹出柱子的高度为基础的矩形，它的左右边界分别是什么。

代码片段：

int width = stack.isEmpty() ? i : i - stack.peek() - 1;

这行代码的作用是计算矩形的宽度，决定矩形的左右边界。我们可以将其分为两个部分来理解。

1. 为什么需要计算宽度？

当我们从栈中弹出一个柱子时，这个柱子的高度成为当前矩形的高度，但我们还需要知道矩形的左右边界才能计算面积。

右边界：当前柱子 i 的索引可以看作是右边界，因为当我们弹出栈顶元素时，当前遍历到的柱子高度 h 比栈顶柱子矮（h < heights[stack.peek()]），因此它限制了栈顶柱子的扩展。
左边界：左边界取决于栈中剩下的下一个元素（也就是当前弹出的柱子左边比它更低的柱子）。如果栈中已经没有元素了，说明弹出的这个柱子可以从索引 0 开始扩展到当前索引 i - 1。

2. 代码解释

int width = stack.isEmpty() ? i : i - stack.peek() - 1;

这行代码是用来计算弹出的栈顶柱子对应的矩形宽度的，有两种情况：

情况 1：栈为空（`stack.isEmpty()`）

说明：当我们弹出栈顶元素后，栈为空，意味着弹出的柱子左边没有任何柱子阻碍它的扩展。因此，弹出的这个柱子可以从索引 0 一直延伸到当前柱子的索引 i - 1。
宽度：在这种情况下，矩形的宽度就是从 0 到 i - 1，即宽度为 i。所以 width = i。
举例：假设栈中只有一个柱子 heights[0] = 5，遍历到 i = 3，此时弹出栈顶，栈变为空，矩形宽度是 3，因为它可以从索引 0 扩展到索引 2，即 width = 3。

情况 2：栈不为空（`!stack.isEmpty()`）

说明：当弹出栈顶元素后，栈中还有其他柱子，这意味着弹出的柱子左边有另一个较低的柱子阻碍它扩展。此时，弹出栈顶柱子的矩形的左边界由下一个栈顶元素（stack.peek()）决定。
宽度计算：矩形的宽度是从下一个栈顶元素的索引 stack.peek() 加 1，到当前柱子之前的索引 i - 1。因此，宽度为 i - stack.peek() - 1。
举例：假设栈中有两个柱子 heights[0] = 5 和 heights[1] = 6，遍历到 i = 3，此时弹出 heights[1]，栈中剩下 heights[0]。弹出 heights[1] 后，宽度是从 stack.peek() 位置（即 0）加 1 到当前索引 i - 1，即 3 - 0 - 1 = 2。

当栈不为空时，我们的目标是计算当前弹出栈顶元素所能形成的矩形宽度，它的左右边界分别是：

右边界：当前遍历到的柱子之前的索引，也就是 i - 1。
左边界：栈中下一个元素的索引 stack.peek()，这个元素是弹出栈顶元素左边的柱子，它限制了弹出柱子的扩展，所以左边界应是 stack.peek() + 1。

因此，宽度的计算可以表示为：

width = (i - 1) - (stack.peek() + 1) + 1

简化后就是：

width = i - stack.peek() - 1

这个公式简洁地表达了矩形的宽度，涵盖了从左边界（stack.peek() 后的那一个柱子）到右边界（当前柱子的前一个位置）的距离。

你已经掌握了宽度计算的关键逻辑，非常棒！

3. 具体示例

我们用 [5, 6, 7, 2] 这个例子来展示如何计算宽度。

初始状态：遍历 5, 6, 7 时，栈依次存入 [0, 1, 2]。
遇到 2 时：2 < 7，开始弹出栈顶元素。
1. 弹出 7（索引 2）：
  - 栈中剩下 [0, 1]，7 的右边界是当前索引 3，左边界是 6 的位置（stack.peek() 为 1）。
  - 宽度为 3 - 1 - 1 = 1，矩形面积为 7 * 1 = 7。
2. 弹出 6（索引 1）：
  - 栈中剩下 [0]，6 的右边界仍然是当前索引 3，左边界是 5 的位置（stack.peek() 为 0）。
  - 宽度为 3 - 0 - 1 = 2，矩形面积为 6 * 2 = 12。
3. 弹出 5（索引 0）：
  - 栈为空，所以 5 的右边界是当前索引 3，而左边界是 0。
  - 宽度为 3（因为栈为空），矩形面积为 5 * 3 = 15。