作者 | 程序员小吴
来源 | 五分钟学算法
小伙伴们都应该非常熟悉栈,栈的一个很鲜明的性质就是:先进后出 。
而所谓 单调栈 则是在栈的 先进后出 基础之上额外添加一个特性:从栈顶到栈底的元素是严格递增(or递减)。
具体进栈过程如下:
e
,从栈顶开始遍历元素,把小于 e
或者等于 e
的元素弹出栈,直接遇到一个大于 e
的元素或者栈为空为止,然后再把 e
压入栈中。e
或者等于 e
的元素。以 单调递增栈 为例进行说明。
现在有一组数
3,4,2,6,4,5,2,3
让它们从左到右依次入栈。
具体过程如下: