数据结构：单调栈

什么是单调栈

单调栈是指从栈顶到栈底，栈内元素的值符合单调性的一种特殊数据结构。从栈顶到栈底，元素的值单调递减，称为单调递减栈；反之，称为单调递增栈。

 \  9  /      \  1  /
 |  7  |      |  3  |
 |  5  |      |  5  |
 |  3  |      |  7  |
 |  2  |      |  9  |
 -------      -------
单调递减栈     单调递增栈

单调栈的维护

为了维持栈的单调性，在往栈内插入元素时，需要比较循环比较栈顶元素与待插入元素的值的大小，以单调递增栈举例，需要始终确保栈顶元素的值大于等于待插入元素的值方可插入，否则需要先弹出栈顶元素之后，重复“检查-弹出”的流程，直到栈为空，或者栈顶元素的值大于等于待插入元素的值。

假设需要插入的元素按照序列 5, 2, 3, 7, 1 从左到右遍历，且需要维护单调递增栈，则插入过程为：

 \     /    \     /    \     /   \     /   \     /
 |     |    |  2  |    |  3  |   |     |   |  1  |
 |  5  |    |  5  |    |  5  |   |  7  |   |  7  |
 -------    -------    -------   -------   -------
   (1)        (2)        (3)       (4)       (5)

(1) 待插入 5，栈为空，直接插入 5；
(2) 待插入 2，栈顶元素为 5，大于待插入元素 2，2 可以直接插入；
(3) 待插入 3，栈顶元素为 2，不满足大于等于 3 的要求，所以弹出栈顶元素 2；此时新的栈顶元素为 5，大于 3，3 直接入栈；
(4) 待插入 7，栈顶元素为 3，不满足大于等于 7 的要求，所以弹出栈顶元素 3；此时新的栈顶元素为 5，仍然小于 7，于是也弹出栈顶元素 5；最后栈为空，直接插入 7；
(5) 待插入 1，栈顶元素为 7，大于待插入元素 1，1 可以直接入栈。

类似地，假如我们翻转下插入的顺序，即按照按照序列 5, 2, 3, 7, 1 从右到左顺序插入单调递增栈，则插入过程为：

 \     /    \     /    \     /   \  2  /   \     /
 |     |    |     |    |  3  |   |  3  |   |  5  |
 |  1  |    |  7  |    |  7  |   |  7  |   |  7  |
 -------    -------    -------   -------   -------

单调栈的性质总结

通过上面的两个例子，可以总结出单调递增栈的性质：

单调递增栈可以表示：按照元素入栈顺序，入栈元素前面比它大的所有元素中离它最近的元素。

更具体地讲，当我们从左到右访问序列时，则单调递增序列表示入栈元素左边所有比它大的元素中，距离它最近的元素，比如第一个例子中，3左边第一个比它大的元素是5，而7左边没有比它大的元素；反过来，当我们从右到左访问序列时，则单调递增序列表示入栈元素右边所有比它大的元素中，距离它最近的元素，比如7右边没有比7大的元素，1右边也没有比1大的元素，而2右边第一个比2大的元素刚好是3，5右边比5大的第一个元素是7。

很容易通过类似的演示归纳总结单调递减栈的性质：

单调递增栈可以表示：按照元素入栈顺序，入栈元素前面比它小的所有元素中离它最近的元素。