单调栈 - Taxodium

定义

单调栈即满足单调性的栈结构，插入时要保证栈的单调性。

它适合解决那些需要找到 下一个/上一个更大/小值 的问题。

按照从 栈顶到栈底 的顺序，递增则为单调递增栈，递减则为单调递减栈。

左侧为栈底，右侧为栈顶：

单调递增栈：[5,4,3,2,1]

单调递减栈：[1,2,3,4,5]

对于单调栈，在 插入 时，需要去比较入栈元素和栈顶元素的大小。

以单调递增栈为例子，要保证从栈顶到栈底是递增的关系。

入栈时，要保持栈顶的元素大于等于入栈的元素。

如果栈顶元素比入栈元素小，则将栈顶元素弹出，直到栈顶元素大于等于入栈元素，或者栈为空。

对于数组 [5,2,3,7,1]

按照从左到右遍历数组，构造单调递增栈(左边栈低，右边栈顶):

[]
[5] 栈为空，入栈 5
[5,2] 栈顶 5 大于 2，入栈 2
[5,3] 栈顶 2 小于 3，弹出 2；弹出后，栈顶 5 大于 3，入栈 3。 观察此时的序列，通过序列可以知道，对于入栈元素 3，左边第一个比它大的元素是 5
[7] 栈顶 3 小于 7，弹出 3；栈顶 5 小于 7，弹出 5；栈为空，入栈 7
[7,1] 栈顶 7 大于 1，入栈 1

对于单调 递增 栈，当 从左到右 遍历进行入栈时，单调递增栈的序列表示的是， 左边第一个大于等于入栈元素的数 。

当 从右往左 入栈时，单调递增栈序列表示的是， 右边第一个大于等于入栈元素的数 。

而单调 递减 栈则可以用来找 第一个比入栈元素小的数 。

有的问题，还需要限制 严格递增或者严格递减 ，即栈序列都是严格递增递减的，不会出现相等的元素，例如739. 每日温度。