在这里插入图片描述

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

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

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

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

步骤解析:

初始化:
  • 我们的输入数组是 [5, 6, 7, 2],依然使用单调栈来计算最大矩形面积。
  • 遍历每个柱子,同时维护一个递增栈(存放柱子的索引)。
遍历开始:
  1. i = 0, heights[0] = 5

    • 栈为空,将 0 压入栈,栈为 [0]
  2. i = 1, heights[1] = 6

    • 栈顶元素对应的高度是 56 > 5,继续保持递增顺序,将 1 压入栈,栈为 [0, 1]
  3. i = 2, heights[2] = 7

    • 栈顶元素对应的高度是 67 > 6,继续递增,将 2 压入栈,栈为 [0, 1, 2]
  4. i = 3, heights[3] = 2

    • 现在,当前柱子 2 < 7,不再递增了,我们需要弹出栈顶来计算面积。
弹栈计算过程:
  1. 弹出 2 索引的柱子 (高度 7)

    • 栈顶的高度是 7,宽度为 1(因为 i - stack.peek() - 1 = 3 - 1 - 1 = 1),即矩形面积为 7 * 1 = 7
    • 更新最大面积为 7
  2. 弹出 1 索引的柱子 (高度 6)

    • 栈顶的高度是 6,宽度为 2(因为 i - stack.peek() - 1 = 3 - 0 - 1 = 2),即矩形面积为 6 * 2 = 12
    • 更新最大面积为 12
  3. 弹出 0 索引的柱子 (高度 5)

    • 栈顶的高度是 5,宽度为 3(因为栈已为空,所以宽度就是 i = 3),即矩形面积为 5 * 3 = 15
    • 更新最大面积为 15
继续遍历:
  1. 压入当前柱子 2
    • 现在将索引 3 压入栈,栈为 [3]
遍历结束:
  1. 遍历结束后,栈中还有元素 3,对应的高度是 2,我们需要处理剩余的栈:
    • 以高度 2 作为最后的矩形,高度为 2,宽度为 4(因为栈为空,宽度就是整个数组的长度 n = 4),即矩形面积为 2 * 4 = 8

最终结果:

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

总结:

  1. [5, 6, 7, 2] 的案例中,当遇到比栈顶更小的 2 时,栈中的元素会依次被弹出,首先以 7 作为高度计算矩形面积,接着以 6,最后以 5。栈底元素 5 也会在这个过程中被正确地弹出,并计算出它作为高度的最大矩形面积,因此最终以栈底元素 5 为高度的矩形仍然会被正确计算

  2. 之所以使用栈顶元素作为 height,是因为栈顶元素对应的柱子是当前需要被“封闭”的柱子,当前柱子限制了栈顶柱子的右边界,所以我们需要计算以它为高度的最大矩形。

  3. 栈底元素最终也会被弹出并处理,只不过它的处理顺序是等到它的右边界被确定之后才会弹出计算,确保不会漏掉任何可能形成的更大矩形。

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
  • 宽度:在这种情况下,矩形的宽度就是从 0i - 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] = 5heights[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]

  • 遇到 22 < 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

4. 总结

  • 宽度的计算逻辑
    • 如果栈为空,说明弹出的柱子可以扩展到最左端,即从 0 到当前索引的前一个位置,宽度为 i
    • 如果栈不为空,说明弹出的柱子左边有其他柱子阻碍,它的左边界由下一个栈顶元素的索引决定,宽度为 i - stack.peek() - 1

通过这行代码,我们可以精确地计算每个弹出栈顶柱子所能形成的最大矩形的宽度,并结合高度一起更新矩形面积。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部