LeetCode 84 柱状图中最大的矩形

本题是一道栈的经典例题，借分析本题引出单调栈相关问题的一般分析方法，避免死记硬背模板代码。

题目描述

原题链接如下： LeetCode 84 柱状图中最大的矩形

题目大意

有 n 个非负整数，分别用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。那么任意多个相邻的柱子就会拼接成不同的封闭图形，其中每个图形必定可以切割出一个矩形。求在该柱状图中，能够用此方法得出的矩形的最大面积。

输入与输出

示例输入为：

1
2

Input:
heights = [2,1,5,6,2,3]

对应输出为：

1
2

Output:
10

解题思路

矩形面积易求，不过是长和宽的乘积，那么我们自然可以使用暴力方法枚举每个柱子对应的矩形的面积，然后求出最大值。枚举的方法也很简单直接，即遍历每个柱子时分别向左右两侧探测，找到比当前柱子高度更低的柱子，这样相应矩形的高就是当前柱子的高，而宽则是左右两侧探测的距离。 这样的枚举算法时间复杂度为 $O(n^{2})$，当然，这样的算法会有大量的重复计算。（例如：考虑一种特殊的输入数据，保证 heights 数据完全相等，那么我们每次都要遍历整个数组才能确定当前的矩形面积。）究其原因在于我们在任意个元素的枚举操作时，已经知道了它和左右两侧元素的大小关系，但是之后的枚举完全没有利用已经计算好的结果，所以优化的思路就是充分利用已经掌握的之前柱子的高度关系。

如果我们要利用空间换时间，那么理想的办法是在处理下标为 i 的柱子时，能利用之前的处理结果，那么枚举时最好就不要向右探测导致数据之间的关系变得极端复杂。但是，我们只向左探测的时候并不能完全确定当前的柱子高度所围成的矩形，毕竟右面可能有比它更高的柱子。那么，不妨我们只在一个柱子比它右侧的邻居高的时候进行向左探测工作，这样只有找到左面的比它低的柱子就结束，如此必定能确定使用当前柱子的高度所围成的矩形。当然，如果柱子不比它右侧邻居更高那我们便无法得知它的右边界，只能缓存它等待合适的处理时机。

换句话说，我们必须保证缓存的柱子高度一定是单调递增的（允许相等元素），一旦新的柱子 i 不符合这一条件，我们就开始向左探测的工作。如此一来，向左探测的工作一旦触发，就要不断取出最新的缓存柱子。不妨设最新的缓存柱子下标为 x，如果它比 heights[i] 大，那么它对应矩形的右边界为 i，它的上一项缓存的柱子不妨设为 y（显然 $y < x$）。既然缓存的柱子高度严格递增，则 $heights[y] \le heights[x]$ 必然成立。而在下标区间 $(y, x)$ 内的柱子虽然都没有缓存，但是根据缓存的规则它们不可能小于 heights[x]，所以下标 x 的柱子对应的矩形我们可以必然确定。以此类推，可以同样确定缓存的其他高度大于 heights[i] 的柱子。

此实例中，我们在遍历 i 为 4 时（高度为 2 的柱子），得到 x 为 6，缓存的数据是 [1, 5, 6]。

另外，我们不在缓存中的下标在区间 $(y, x)$ 内的柱子其高度必定大于 heights[x]，只要使用同样的处理办法，那么它们对应的矩形我们便早已确定（最迟被 x 柱子触发探测动作），所以不缓存它们不会影响 x 柱子的探测工作。 显然，经过以上的分析，我们的缓存结构是需要保证数据单调递增，同时方便按 heights 下标从左向右存储和从右向左取出进行探测工作，即单调递增栈。另外，我们使用缓存的柱子既要获取它的高也要知道它的下标方便计算矩形宽度，不妨直接缓存下标。

最后，我们的柱子在最左和最右的下标处需要额外处理，那么不妨复制原始数据给它们增加新的虚拟左右边界柱子，高度为 0，可以保证逻辑一致的同时省去额外的条件判断。 这样，得到的算法过程如下：

1. 复制原始数据，增加哨兵柱子
2. 初始化一个空栈，然后存入第一个柱子的下标
3. 遍历剩余的柱子，对应每个待遍历的下标为 i 的柱子判断它和栈顶柱子的高度
   • 如果栈顶柱子高于 heights[i] 则：
     1. 出栈，并获取其高度 h
     2. 新栈顶下标和 i 之间的柱子数量是矩形宽度 w
     3. 得到一个新的矩形面积为 $w \cdot h$，和旧矩形面积取最大
   • 如果栈顶柱子不高于 heights[i] 则下标 i 入栈

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.ArrayDeque

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        var area = 0
        val stack = ArrayDeque<Int>()
        val newHeights = IntArray(heights.size + 2)
        heights.copyInto(newHeights, 1)
        stack.push(0)
        for (i in 1 until newHeights.size) {
            while (newHeights[stack.peek()] > newHeights[i]) {
                val height = newHeights[stack.pop()]
                val width = i - stack.peek() - 1
                area = maxOf(area, height * width)
            }
            stack.push(i)
        }
        return area
    }
}

因为栈的最大尺寸已知，也可以使用静态数组代替容器操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        var area = 0
        val newHeights = IntArray(heights.size + 2)
        val stack = IntArray(newHeights.size)
        heights.copyInto(newHeights, 1)
        stack[0] = 0
        var top = 0
        for (i in 1 until newHeights.size) {
            while (newHeights[stack[top]] > newHeights[i]) {
                val height = newHeights[stack[top--]]
                val width = i - stack[top] - 1
                area = maxOf(area, height * width)
            }
            stack[++top] = i
        }
        return area
    }
}