Contents
[NOTE] Updated May 31, 2023. This article may have outdated content or subject matter.
单调栈即满足单调性的栈结构，插入时要保证栈的单调性。
它适合解决那些需要找到 下一个/上一个更大/小值 的问题。
按照从 栈顶到栈底 的顺序，递增则为单调递增栈，递减则为单调递减栈。
左侧为栈底，右侧为栈顶：
单调递增栈：[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. 每日温度。
-
要寻找
更小值，那么就要形成变 “小” 的单调栈，所以选择单调递减栈，如果要找左边第一个更小值，就从左边开始遍历 -
要寻找
更大值，那么就要形成变 “大” 的单调栈，所以选择单调递增栈，如果要找左边第一个更大值，就从左边开始遍历