单调栈是什么？

引子

单调栈是一种特别设计的栈结构，为了解决如下的问题：

给定一个可能含有重复值的数组 arr，$i$ 位置的数一定存在如下两个信息：

• 1）arr[i] 的左侧离 $i$ 最近并且小于（或者大于）arr[i] 的数在哪？
• 2）arr[i] 的右侧离 $i$ 最近并且小于（或者大于）arr[i] 的数在哪？

如果想得到 arr 中所有位置的的两个信息，怎么能让得到信息的过程尽量快？那么到底怎么设计呢？

流程

• 数组无重复值的情况

假设数组为 [3, 4, 2, 6, 1, 7, 0, 5]，准备一个栈，从栈底到栈顶的元素（栈中存放的是数组下标）对应的值从小到大。

记录 $a$ 位置的 $b$ 值为 $a$->$b$。

首先因为栈为空，所以 0->3 入栈；

接着，1->4，因为 4 > 栈顶的3，没有破坏从小到大的原则，所以可以直接入栈。此时栈底到栈顶：[0->3，1->4]

接下来到了 2->2，因为 2 < 栈顶的4，所以栈顶的 4 出栈，此时就得到了1->4的左侧离它最近的小于它的数为栈中在它下面的0->3，而右侧离它最近的小于它的数为使得它从栈中出来的数，即2->2。【1->4的左侧比它小的数是0->3，右侧比它小的数是2->2】

此时2->2应该入栈，但是因为 2 < 3，所以0->3出栈，弹出的时候收集信息，得到3右侧比它小的数是 2->2，而3的下面有没有压着任何数，所以它左边比它小的数不存在，即位置为-1。

然后2->2入栈，此时栈底到栈顶：[2->2]

接下来到3->6，6 > 2，可以直接入栈，[2->2， 3->6]

接着是4->1，1 < 6，所以6出栈，出栈时收集信息，6 左侧比它小的是它压着的数即2->2，右侧比它小的是使得它出栈的4->1。

4->1 < 栈顶的2，所以 2 出栈，收集2的相关信息，左侧比它小的不存在，所以-1，右侧比它小的是4->1。

此时栈空，4->1可以入栈。

…

数组遍历完后，单独弹出栈中的信息。

最后栈中从栈底到栈顶的情况[6->0，7->5]，弹出栈顶的5，因为并不是因为某个其他数弹出的，而是单独弹出的，所以右侧没有比5小的数，那么就记录右侧比它小的数的位置为数组长度；而左边离它最近比它小的数就是栈中它压着的数，即6->0。

最后，6->0弹出，左右都没有比它小的数，记录左边比它小的数的位置为-1，右边比它小的数的位置为数组长度。

最后整个信息都收集完成了。

因为对于每个位置来说，它最多进栈一次出栈一次，所以得到所有位置的信息时间复杂度是 $O(n)$

• 为什么流程对？

假设此时从栈底到栈顶从小到大的情况：[… $a$, $b$]，则 $a<b$

一个数要从栈中弹出的时候，为什么当前数就是右边离它最近比它小的数：当前遍历到 $c$，如果 $b>c$，那么 $b$ 就需要从栈中弹出，首先可以确定，$b$ 在 $c$ 的左边，那么在 $b$…$c$ 中间的数是不可能有比 $b$ 小的数的，否则 $b$ 早就从栈中弹出了。现在轮到 $c$ 使得 $b$ 从栈中弹出，说明 $c$ 就是离 $b$ 最近的比 $b$ 小的数。

为什么 $b$ 的左边离它最近比它小的数是 $a$ 呢？在栈中，$b$ 在 $a$ 的上面，则说明在数组中 $a$ 在 $b$ 的左边，$a$…$b$，如果它们中间存在数，就分几种情况：

1. 中间的数 < $a$，那么 $a$ 早就出栈了，就不会出现 $a$ 和 $b$ 相邻情况，所以可以证明，中间的数一定不会小于 $a$；

2. 如果 $a<$ 中间的数 $<b$，不可能。比如[3, 5, 4, 7]，如果出现这种情况，那么 3 和 7 之间一定隔着某个数，而不会是相邻的；

3. 如果中间的数 > $b$，是有可能的，而此时栈中 $a$ 挨着 $b$，那么就证明了 $a$ 就是 $b$ 左边第一个比它小的数。

单独结算的时候，能在栈中的数，说明右边没有比它小的数，否则它不可能在栈中。

• 数组中有重复值的情况

例如数组：[1，3，4，5，4，3，1，2]

同样准备一个栈，从栈底到栈顶的元素对应的值由小到大。

因为存在重复数字，所以每个进入栈中的数字要在自己的位置形成一个链表。

首先 0->1，因为栈为空，可直接进入栈中，但是 0 位置要形成一个链表 【{0}->1】

然后 1->3，因为3 > 1，所以可以直接入栈，同理 1 位置要形成一个链表 【{0}->1、{1}->3】

然后 2-> 4，因为 4 > 3，可直接入栈，同理 2 位置要形成一个链表 【{0}->1、{1}->3、{2}->4】

然后 3->5，因为 5 > 4，可直接入栈，同理 3 位置要形成一个链表 【{0}->1、{1}->3、{2}->4、{3}->5】

然后 4->4，因为 4 < 5，所以栈顶的 5 出栈，结算答案。让它出栈的 4->4 就是右侧比它小的第一个数，而在栈中它压着的链表的最后一个位置 即 2->4 是左侧比它小的第一个数；【{0}->1、{1}->3、{2}->4】

接着 4->4 要入栈，因为 4 = 4，不能直接放在 4 上面，所以插到2位置后面形成链表 【{0}->1、{1}->3、{2,4}->4】

然后 5->3 要入栈，因为 3 < 4，所以此时 2->4 和 4->4 一起结算，4->4 右边第一个比它小的数是 5->3，左边比它小的第一个数是它在栈中压着的链表的最后一个位置的值即 1->3；2->4 同理。就是说同一个链表中出来的结果是一样的。【{0}->1，{1}->3】

接着 5->3 要入栈，因为 3 = 3，所以两个位置的3放到同一个链表中 【{0}->1，{1,5}->3】

…

注意

• 实际实现过程中，为了获取首尾的值的快捷，用的是$O(1)$ 复杂度的结构，比如数组实现，而非$O(n)$ 复杂度的链表；
• 其次，因为系统提供的栈中使用了动态数组，为了优化时间复杂度，通常都使用自己实现的栈替代系统提供的栈。