数据结构:单调栈

什么是单调栈

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

 \  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。

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

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