刚好是 10 月 24 日程序员日，拖更了一万年的我决定来稍微写点东西。
来看看算法题里面的经典套路之单调栈吧。
认识单调栈
首先来看这样一个数组：[3, 1, 5, 8, 6, 4, 7, 2, 9]，假设每个数字都等于这个数的身高，考虑这样一个问题：对于数组中的每个数，它左侧比它高的数里，离它最近的是谁？
逐一查看，我们可以写下答案：[-1, 3, -1, -1, 8, 6, 8, 7, -1]。但是如何用算法来解决这个问题？
首先考虑最左边的 3，由于它是最左侧的元素，直接标记下标 0 的答案为 -1，但是 3 可能成为后面的答案，所以我们可以拿一个「小本本」写下 3。
接下来是 1，我们检查「小本本」，发现它左侧的 3 比它高，所以下标为 1 的答案为 3。同样地，我们把 1 写进「小本本」。
再然后是 5，「小本本」上没有比它高的元素，因此填上 -1。这时我们可以发现一个问题，对于 5 右边的所有元素，答案都不再可能是 1 或者 3，因为如果一个数小于 3，那么必然也小于 5，而 5 比 3 离这些数都更近。
于是，我们在把 5 写进「小本本」之前，可以直接把 1 和 3 全部清空，因为它们不可能再成为答案了。
同样的道理，在把 8 写进「小本本」之前，我们可以清空 5；在把 7 写进「小本本」之前，我们可以清空 4 和 6，但左侧的 8 依然保留，因为不确定后面是不是会有另一个 7。
发现了吗，我们在做这样一些事情：
- 每当遇到一个数
x，我们检查「小本本」，从右边开始逐个进行比较，如果「小本本」最右侧这个数小于x，那么它不再具有利用价值，我们将它删除； - 当发现小本本最右侧的数比
x大，我们就停止这次删除，此时「小本本」上的数肯定都比x大； - 最后，我们把
x加入到「小本本」的最右边。
我们在线性数据结构的同一侧（右侧）添加与删除元素，这是栈；与此同时，栈内的元素是递减的，因此我们称它为单调栈。单调栈就类似于汉诺塔，在摆放更大的圆盘前，需要先从下方移出比它小的圆盘。
132 序列
对于一个数组 arr，如果存在下标 i, j, k 使得 arr[i] < arr[k] < arr[j]，我们称这三个元素是 arr 的一个 132 序列。比如说上面数组里的 [3, 8, 6] 就是。
要解决的问题是，怎么判断一个数组是否包含 132 序列？
首先对于这类问题，肯定是要遍历，但遍历顺序怎么确定？我们把 132 序列里的三个元素分别称作 A, C, B，那么 A 既是三个数里最靠左的，又是最小的，所以从右往左去找 A 肯定最方便。因此我们可以这么做：
- 维护一个数据结构，然后从数组最右边开始遍历；
- 每遇到一个数
x：x可能是 B，所以我们把它加入到数据结构中去，方便后两步查阅；x可能是 C，所以我们比较数据结构中的数，如果比 C 小，那么它很可能是 B 的候选人，从中选出最大的 B 的候选人，方便后续找 A；x可能是 A，如果说之前已经发现了比x大的 B 的候选人，那么直接让x作为 A，我们就找到了一个 132 序列。
同时，我们可以发现一件事，随着遍历过程的进行，B 的候选人只会不断变大。这也就意味着，一旦一个数成为 B 的候选人，它在后续的遍历过程里对 B 的候选人的更新就不会再起到任何作用，因此我们可以直接把它踢出数据结构。
数据结构里的数从右侧添加、从右侧踢出、保持单调递减的顺序，这正是前面提到的单调栈。我们直接来看代码：
func find132pattern(arr []int) bool {
n := len(arr)
stk := []int{ arr[n-1] }
max := func(a, b int) int { if b > a { return b }; return a }
maxB := math.MinInt
for i := n-2; i >= 0; i-- {
x := arr[i]
// x 小于 B 的候选人，直接当成 A，找到 132 序列
if x < maxB {
return true
} else if x == maxB {
// x 等于 B 的候选人，那么它不可能成为更有价值的 B 或 C，直接无视
continue
}
m := len(stk)
// 把 x 视为 C，考察栈内所有比 x 小的元素，更新 B 的候选人
for m > 0 && x > stk[m-1] {
// 如果单调栈栈顶元素比 x 小，比 B 的候选人大，就让它成为新的 B 的候选人
maxB = max(maxB, stk[m-1])
// 栈顶元素已经完成使命，通过向左移动指针来模拟将它踢出
m--
}
// 把 x 加入单调栈，期待它和栈内存活的其他数成为新的 B 的候选人
stk = append(stk[:m], x)
}
// 遍历完成没找到 132 序列即返回 false
return false
}
另辟蹊径
上面的方法的时间、空间复杂度均为 $O(n)$，其中 $n$ 是数组的长度。虽然这已经很高效地解决了问题，但是从右向左遍历的缺陷在于需要提前知道数组的长度。如果数组是以数据流的形式给出，就不方便使用这样的方式来进行判断。
因此，如果是从左向右遍历，有没有办法解决这个问题？
在从右往左的方法里，之所以我们可以维护一个全局最大的 B 的候选人，是因为这种做法能保证 C 在 B 的左侧。但是在从左往右的方法里，我们不能维护一个全局最小的 A 的候选人，因为我们不能保证 C 在 A 的右侧。
既然如此，我们对于每个 C 都维护一个 A 的候选人，不就能够解决问题了吗？思路如下：
- 维护一个数据结构，然后从数组最左边开始遍历；
- 每遇到一个数
x：x可能是 A，我们拿x和x左侧的最小值比较，选出较小的那个成为当前位置的 A 的候选人；x可能是 C，所以我们把它加入到数据结构中去，方便后面查阅；x可能是 B，寻找x左侧比x大的离x最近的数作为 C，然后查找 C 左侧 A 的候选人，如果满足x大于 A 的候选人，我们就找到了 132 序列。
关于「寻找 x 左侧比 x 大的离 x 最近的数作为 C」，这不正是开篇引入单调栈时提出的问题吗？因此直接套用思路即可：
func find132pattern(arr []int) bool {
min := func(a, b int) int { if b < a { return b }; return a }
leftMin := make([]int, len(arr))
leftMin[0] = arr[0]
stk := []int{ 0 }
for i, v := range arr[1:] {
// 对于每个下标 i，确定 arr[0..i] 内的最小值，作为 A 的候选人
leftMin[i+1] = min(leftMin[i], v)
m := len(stk)
// 使用单调栈及时踢出不可能再成为 C 的数
for m > 0 && v >= arr[stk[m-1]] {
m--
}
// 把 x 加入单调栈，期待它和栈内存活的其他数成为新的 C
stk = append(stk[:m], i+1)
// 如果栈非空，则令栈顶元素为 C，观察 A 的候选人是否小于 x，小于则找到 132 序列
if m > 0 && stk[m-1] > 0 && leftMin[stk[m-1]-1] < v {
return true
}
}
return false
}
需要特别注意的一点是，由于 leftMin 需要靠 arr 中的下标来查找 A 的值，因此单调栈中我们不直接存储 C 的值，而是存储 C 对应于 arr 的下标。这种存储下标的做法在单调栈的使用中非常常见。
解法二相对解法一在代码编写上更加简洁，需要额外维护一个 leftMin 数组，时间、空间复杂度同样为 $O(n)$，建议两种思路都理解与掌握，在遇到类似问题时能够从不同角度出发来进行思考。
好的，今天的单调栈小知识就分享到这里吧，程序员日快乐哟 OwO。