引子

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

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

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

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

流程

• 数组无重复值的情况

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

记录 aaa 位置的 bbb 值为 aaa->bbb。

首先因为栈为空，所以 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，7->5，-1】

最后，6->0弹出，左右都没有比它小的数。

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

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

• 为什么流程对？

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

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

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

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

2）如果 a

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