单调栈巧解柱状图最大矩形
这几天群里打卡的几道题都是十分经典的面试题，经典是因为这些题都是一题多解的。在这些高效的解法中，单调栈是一个很有技巧的解法，所以这一次我们来聊聊这个单调栈。
所谓单调栈（Monotone Stack）听上去很高端，其实就是字面的意思：栈内元素都是单调递增或者单调递减的。如上图，就是一个从栈底到栈顶的单调递增栈，当然还有另外一种就是单调递减栈。你可能会想这种数据结构到底有什么作用？其实这个数据结构并没有任何高效操作，而是因为它在某些问题中是一个巧妙的解法。到底如何巧妙，我们下面来看两道例题。
[LeetCode-84] 柱状图中最大的矩形
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为
1，给定的高度为[2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例输入
输入: [2,1,5,6,2,3]
输出: 10
如何入手
首先来这么考虑，“能够勾勒出的最大矩形面积” 意味着如果我们可以枚举所有的矩形大小，就可以找到最大的矩形面积。但是这最少需要 O(n^2) 的复杂度，也并不是我们想要的解答方法。
接下来我们想如何使用上文所说的单调栈来解决这个问题。
首先来考虑，这道题我们应该如何获取到这几块矩形的面积？我们可以想到一个最简单到逻辑，因为每一个颜色的矩形，其实都有一个触顶的矩形。所以一个最简单粗暴的思路就是枚举每一个竖直方向的矩形，然后向两边扩展即可。但是这样又会造成 O(n^2) 的开销。
右侧相邻矩形永远小于成块矩形高度
继续查看上面三个高亮的矩形，其实还有一个规律：所有的成块矩形（使用图表中某一个矩形向两边扩散围成的最大矩形）后面的矩形，都会比成块矩形高度要小。这是肯定的，因为如果要是大于等于，则还可以向右继续扩展。我们发现了这个规律，再来观察下面的两幅图。
为什么我要把这两个矩形挑出来，有一个很有趣的规律。我们注意到图中具有高亮的这个矩形，都要比相邻右侧的矩形要高。所以我们完全可以猜想这两个矩形可能是在同一时机被处理。也就是说，当我们从左向右遍历矩形的时候，当发现 height[i] < height[i - 1] 的时候，我们会从 i 这个位置向左遍历，直到找到第一个 height[j] < height[i] 的矩形，停止内层遍历。在这个过程中，我们要不断地更新结果，例如图中的 A、B 这两个情况。我们用动图来描述一个这个情况：
计算面积
这只是我们猜想的一个规律，还有一些情况我们没考虑到。抛开那个话题，先来看一个一般性问题：如何计算矩形面积？看上面的 B 图，我们将高亮的地方单独拿出来看。由于内层的遍历，我们知道当前处理矩形的下标，所以根据夹闭的两端下标以及当前处理的 j 矩形高度直接通过面积公式计算成块矩形的面基。
遍历次数并不是矩形宽度
继续猜想，所以此时仅仅需要知道该矩形是第几次遍历，假设是第 K 次，那么围成的矩形面积即为 K * height[j]。我们似乎发现了一种通用规律，但其实离正确的做法还剩一步。到底最后的坑在哪里，来看下面的这个例子。
当我们继续遍历到箭头所指向的最后一个矩形的时候，我们继续按照上面的规律来计算矩形。此时有两个问题：
- B 情况与之前的 B 情况也是类似的场景，但是此时的 B 情况是其最佳解吗？
- 为什么遍历五个矩形只出现了三种情况？还有情况 D 和情况 E 吗？
问题 1
这个问题还是很好解决的，B 情况自然不是当前高度的最佳情况。因为有如下 B' 情况可使得其达到最佳状况。
我为所有的矩形增加编号，让下文的描述更清晰。其实发现的规律就是，5 号矩形高度所围成的最大矩形情况其实是和 2 号矩形相关系的。为什么？因为在上文中，当我加入 5 号的时候，3 号和 4 号的高度都比 5 号大，则以 3 号和 4 号高度的矩形情况我们已经处理完了，当后续矩形在二次遍历的时候，3 号和 4 号的高度肯定是大于这个边界矩形的。
此时你有没有一种感觉，其实我们一直在维护一个单调递增的序列，如果后续矩形的高度大于末尾，我们会反复的进行计算，并且把末尾的矩形更新成新加入的矩形。这个感觉是对的，越来越逼近单调栈。
问题 2
如问题1 所描述的，此时 3 号和 4 号矩形已经是我们处理过的。其实我们可以把这个问题继续转化成 B'' 这种情况。
此图中虚线代表已经处理过的矩阵，紫色代表加入我们处理序列的数组。我们来维护这个数组处于一个单调递增的状态，当遇到新的矩形高度小于末尾矩形的时候，就不断的弹出末尾元素，进行刚才我们猜想的处理，直到找到第一个比它高度小的元素。
其实这就是在维护一个单调栈。
推导面积计算规律
再来看上面的 B' 情况，我们应该如何计算矩形 5 高度围成的最大矩形面积呢？我用下图来解释：
这里解释一下图中出现的几个元素。栈即为本文所描述的单调栈，用来维护一个待处理矩形下标，并且矩形的高度是单调递增的。当前处理矩形 i 代表最外层遍历处理的矩形，由于图中的 i 矩形高度是小于栈顶矩形高度的，所以开始进行弹栈操作。每一次弹栈的矩形是 cur 矩形，由于将要弹出，则进行一次以 cur 矩形高度为准的最大面积矩形的计算。
在图中，我们给出了其计算公式，S = (i - stack[top] - 1) * height[cur] 。其中 (i - stack[top] - 1) 其实就是为了计算出矩形的长。为什么是从 stack[top] 到 i - 1 呢？因为 cur 右侧一直到 i - 1 号矩形都比 cur 要高，这是单调栈的特性。而 cur 到 stack[top] 之间虽然在栈中是没有矩形的，却是有距离的。如图所示，3 号和 4 号矩形是我们之前相同方式弹出的两个高矩形。这也就是为什么我们需要记录矩形的下标来入栈，其实是为了计算其长度。
动图演示
图示中我们使用上文中的那个矩形图来作为用例，并且给每个矩形赋高度。则使用单调栈来解决这个最大面积，即为演示文稿中的方法求解。
剩余栈的处理的 trick 方案
在图中的演示中，我们发现到最后其实栈中还是有元素未处理完的，所以我们在使用单调栈场景的最后，要单调对栈中元素主动弹栈，并执行相同的查找面积最大值的逻辑。
但其实有一种更为 trick 的方案，就是我们主动在矩形图的末尾增加一个高度为 0 的矩形，这样栈在处理的时候就会主动弹栈，也就不用考虑处理剩余栈的情况来。这种解决方案看似十分 trick，实际上单调栈的题目为了写法方便，往往都会这么做。
代码实现
知道了上述逻辑，就可以进行代码编写了。这里我用 Python 写一版作为示例。
class Solution:
def largestRectangleArea(self, heights) -> int:
stack = []
# 前后插 0，处理余剩栈的情况
heights = [0] + heights + [0]
n, res = len(heights), 0
for i in range(n):
# 如果发现处理的矩形高度小于站顶矩形高度，则弹栈，通过上述方法来计算
while stack and heights[stack[-1]] > heights[i]:
cur = stack.pop()
res = max(res, (i - stack[-1] - 1) * heights[cur])
# 维护栈结构，保证单调递增
stack.append(i)
return res
总结经验
其实单调栈的题目并不是很容易想到这个思路。目前我能总结到的只有多刷相关题目来提升熟练度。下面是我汇总的各个平台的单调栈专题，可以按照这个列表来刷。
- [LeetCode-42] 接雨水
- [LeetCode-239] 滑动窗口最大值
- [LeetCode-496] 下一个更大元素 I
- [LeetCode-503] 下一个更大元素 II
- [LeetCode-739] 每日温度
- [LeetCode-901] 股票价格跨度
- [HDU-5749] Colmerauer
- [HDU-4252] A Famous City
- [HDU-1506] Largest Rectangle in a Histogram
- [HDU-6319] Ascending Rating