[84][困难][栈] 柱状图中最大的矩形

题目描述

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

解题思路

暴力枚举

理解本题单调栈的做法, 需要先从暴力思路开始. 枚举以每个柱形为高度的最大矩形的面积. 具体来说, 遍历每个柱, 对于每一个的高度向左右两边扩散, 求出以当前高度为矩形的最大宽度多少.

这样的方法时间复杂度是$O(n^2)$.

单调栈

是不是可以一次遍历, 不需要对每个柱进行中心扩散, 就能够计算出每一个高度所对应的那个最大面积矩形的面积呢?

因此需要以空间换时间, 这里需要使用的数据结构就是单调栈.

以数组[2, 1, 5, 6, 2, 3]为例.

• 对于第一个高度为2的柱子, 此时以它的高度对应的最大面积还不确定, 因为我们知道了它的左边界, 但右边界还没有确定. 将其加入栈中
• 然后看到了高度为1的柱子, 它对应高度的最大面积肯定也是不确定的. 但它之前高度为2的柱子对应的最大面积已经可以确定了, 因为1限制了它的右边界

  计算高度为2柱子对应的最大面积. 它的高度为2, 与阻碍它向右延伸的高度为1的柱子间隔为1-0=1, 因此对应的最大面积为2. 在一个柱子的最大面积确定后, 就可以从栈中弹出了, 对之后的计算不产生影响, 原因后面会体现.

  将新的为确定最大面积的高度为1的柱子压入栈.

• 遇到高度为5的柱子, 同样对应的最大面积为止. 这时再看下栈中的高度为1的柱子, 5的出现并没有影响它向右扩展, 因此它的最大面积也还不能确定. 将高度为5的柱子压入栈中
• 同样对于高度为6的柱子, 它自身, 以及栈中的高度为1, 5的柱子都没有确定右边界, 不能出栈. 将高度为6的柱子压入栈中
• 遇到高度为2的柱子, 它本身的最大面积肯定是还没有确定的. 但栈顶高度为6的柱子的最大面积可以确定了, 它的左侧被新的高度为2的柱子卡住, 右侧被高度为5的柱子卡住, 因此对应的最大面积为6, 这是因为它左右两侧柱子围住的宽度为6-4-1=1

  而且弹出6后, 此时的新栈顶, 高度为5的柱子的最大面积也确定了, 它的左侧被1位置的柱子卡住, 右侧被4位置卡住, 对应的宽度为4-1-1=2, 因此对应的高度为10.

  将其高度为5, 位置为2的柱子也弹出, 将位置4的柱子压入.

• 遇到最后一个柱子, 也无法判断对应的最大面积, 压入栈

总结上面的步骤:

• 遇到当前柱形的高度比它上一个柱形的高度严格小的时候, 说明栈中至少有栈顶一个柱子的右侧延伸到头了

  • 而这些柱子的左侧最近的一个比它矮的柱子一定还在栈中. 因为这个柱子进来的时候, 会将栈中比它高的柱子弹出

  • 这些更高的柱子可以被弹出并忽略, 因为他们已经不妨碍后面新柱子向左的扩展, 新柱子只需要找到向左穿过这些更高柱子后最近的一个矮柱子

  • 被弹出的柱子对应的最大面积已经确定了, 与全局变量比较并更新

  • 由于更高的柱子被弹出, 这个最近的更矮的柱子就是栈中的下一个元素(重复的情况之后讨论)

• 栈中除了记录柱子的高度, 还要记录柱子的位置, 这样才能计算宽度

此时的栈中还有还有3个柱子:

现在这三个柱子的高度也可以确定了, 因为他们的左右边界都已经确定了.

• 对于最后一个高度为3的柱子, 它的是数组的右侧边界, 而它的左侧边界就是栈中的下一个元素, 因此对应的宽度为5-4=1, 最大面积为3
• 位置4的柱子向右可以延伸到右侧边界, 向左可以延伸到栈中的下一个元素, 对应宽度为5-1=4, 因此对应的最大面积为8
• 最后还剩一个高度为1的柱子, 它向右也可以延伸到右侧边界, 左侧可以延伸到栈的下一个元素. 但此时栈中只有它一个元素, 所以说明它可以向左延伸至左侧边界, 因此对应的宽度为整个数组的长度6, 对应的最大面积是6

这一步可以总结如下:

• 最后还在栈中的柱子, 说明他们向右都可以扩展到右侧边界

• 他们的左侧边界跟之前一样, 也是各自所紧邻栈中的下一个元素

因此观察整个过程中更新栈的逻辑, 遇到更大值时直接压入栈, 遇到下一个较小值时, 将栈顶比这个值大的元素都弹出, 再将其入栈, 因此保持了一个单调递增栈的结构. 之所以使用单调栈的结构, 前面已经提及, 即这些更高的柱子可以被弹出并忽略, 因为他们已经不妨碍后面新柱子向左的扩展, 新柱子只需要找到向左穿过这些更高柱子后最近的一个矮柱子. 我们可以使用单调栈的性质, 快速找到左侧最近的更矮的柱子. 而右侧的边界则可以在遍历过程中确定.

重复元素

还需要考虑的一个细节是, 在确定一个柱形的面积的时候, 除了右边要比当前严格小, 左边也要比当前高度严格小. 如果遇到相同高度的柱子该怎么办?

在右边遍历的时候, 如果遍历到的当前柱子与栈顶柱子的高度相等, 那么栈顶柱子向右发展实际上没有受到阻碍, 因此无需弹出, 直接将新的柱子压入.

在弹出栈中元素时, 被弹出的柱子需要确定它左边的边界. 一般它的左侧边界就是紧邻的栈中下一个柱子, 但可能下一个柱子的高度与这个柱子相同, 那下一个柱子肯定不是左侧边界.

但其实在计算被弹出柱子的面积时, 它的右侧是确定的, 就是当前触发栈中元素弹出的位置. 因此栈中几个相邻的同样高度的柱子都会被弹出, 那么这些同样高度柱子最左侧的一个, 对应的面积是真正的这个高度对应的最大面积, 而最左侧的这个柱子的左侧边界就是它的下一个元素.

那么相同高度的其他几个柱子对应的面积也就不重要了, 可以不考虑, 因此可以保持找下一个元素的计算方式, 保持逻辑的一致性.

哨兵

可以看到上面的处理过程有两个特殊点:

• 最终栈中还是有元素, 需要再次遍历一遍栈

• 如果栈中只有一个元素, 这个元素出栈时, 相当于它的左侧边界为最左侧

因此可以在左右两侧各添加一个高度为0的哨兵(只要比最小高度1更小就可以). 有了这两个柱形哨兵:

• 左边的哨兵由于一定比输入数组里任何一个元素小, 它肯定不会出栈, 因此栈一定不会为空

• 右边的哨兵也正是因为一定比输入数组里任何一个元素小, 它会让所有输入数组里的元素出栈

对应的代码为:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0]  # 添加左右哨兵
        stack = [0]  # 左侧哨兵入栈
        max_area = 0

        for i in range(1, len(heights)):
            while heights[i] < heights[stack[-1]]:
                index = stack.pop()
                h = heights[index]
                max_area = max(max_area, (i - stack[-1] - 1) * h)
            stack.append(i)

        return max_area

参考资料

• 暴力解法、栈（单调栈、哨兵技巧）