单调栈
定义
单调栈即满足单调性的栈结构，插入时要保证栈的单调性，适合解决那些需要找到 下一个/上一个 更大/小值 的问题。
按照从 栈顶到栈底 的顺序，递增则为单调递增栈，递减则为单调递减栈。
单调递增栈：（栈底） [5,4,3,2,1] （栈顶）
单调递减栈：（栈底） [1,2,3,4,5] （栈顶）
性质
对于单调栈，在入栈时，需要去比较入栈元素和栈顶元素的大小。
以单调递增栈为例子，要保证从栈顶到栈底是递增的关系，入栈时，要保持栈顶的元素大于等于入栈的元素。如果栈顶元素比入栈元素小，则将栈顶元素弹出，直到栈顶元素大于等于入栈元素，或者栈为空。
例如，对于 [5,2,3,7,1] ，按照从左到右遍历数组，构造单调递增栈（左边栈低，右边栈顶）:
- 初始化
- 栈为空 →
[] - 5
- 栈为空，入栈 5 →
[5] - 2
- 栈顶 5 大于 2，入栈 2。→
[5,2] - 3
栈顶 2 小于 3，弹出 2；弹出后，栈顶 5 大于 3，入栈 3。→
[5,3]观察此时的单调栈里的序列，可以知道，对于入栈元素 3，左边第一个比它大的元素是 5。
- 7
- 栈顶 3 小于 7，弹出 3；栈顶 5 小于 7，弹出 5；栈为空，入栈 7。 →
[7] - 1
- 栈顶 7 大于 1， 入栈 1。→
[7,1]
也可以从右到左遍历数组，还是以 [5,2,3,7,1] 为例：
- 初始化
- 栈为空 →
[] - 1
- 栈为空，入栈 1。→
[1] - 7
- 栈顶 1 小于 7，弹出 1；弹出后栈为空，入栈 7。→
[7] - 3
- 栈顶 7 大于 3，入栈 3。→
[7,3] - 2
- 栈顶 3 大于 2，入栈 2。→
[7,3,2] - 5
2、3 都小于 5，弹出 2、3；7 大于 5，入栈 5。→
[7,5]观察此时单调栈里的序列，可以知道，对于入栈元素 5，右边第一个比它大的元素是 7。
对于单调递增栈，当从左到右入栈时，表示的是左边第一个大于等于入栈元素的数；当从右往左入栈时，表示的是右边第一个大于等于入栈元素的数。
而单调递减栈则可以用来找第一个比入栈元素小的数。
有的问题，还需要限制严格递增或者严格递减，即栈序列都是严格递增递减的，不会出现相等的元素，例如 739. 每日温度。
巧记
要寻找 更小值 ，那么就要形成变「小」的单调栈，所以选择 单调递减栈 ，如果要找 左边 第一个更小值，就从 左边 开始遍历原始数组；如果要找 右边 第一个更小值，就从 右边 开始遍历原始数组。
要寻找 更大值 ，那么就要形成变「大」的单调栈，所以选择 单调递增栈 ，如果要找 左边 第一个更大值，就从 左边 开始遍历原始数组；如果要找 右边 第一个更大值，就从 右边 开始遍历原始数组。
