什么是单调栈
单调栈是指从栈顶到栈底,栈内元素的值符合单调性的一种特殊数据结构。从栈顶到栈底,元素的值单调递减,称为单调递减栈;反之,称为单调递增栈。
\ 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。
很容易通过类似的演示归纳总结单调递减栈的性质:
单调递增栈可以表示:按照元素入栈顺序,入栈元素前面比它小的所有元素中离它最近的元素。
版权声明:本文为原创文章,转载请注明来源:《数据结构:单调栈 - Hackerpie》,谢绝未经允许的转载。