参考链接：https://github.com/itcharge/LeetCode-Py
一、简介
单调栈（Monotone Stack）：一种特殊的栈。在栈的「先进后出」规则基础上，要求「从栈顶到栈底的元素是单调递增（或者单调递减）」。其中满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」。
1.1 单调递增栈
单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。
这样就保证了：栈中保留的都是比当前入栈元素大的值，并且从栈顶到栈底的元素值是单调递增的。
单调递增栈的入栈、出栈的过程：
- 假设当前进栈元素为 x，如果栈顶元素大于 x，则直接入栈。
- 否则从栈顶开始遍历栈中元素，把小于 x 或者等于 x 的元素弹出栈，直到遇到一个大于 x 的元素为止，然后再把 x 压入栈中。
实例：
-
数组元素：[2, 7, 5, 4, 6, 3, 4, 2]，遍历顺序为从左到右。
image.png
最终栈中元素为 [7, 6, 4, 2]。因为从栈顶（右端）到栈底（左侧）元素的顺序为 2, 4, 6, 7，满足递增关系，所以这是一个单调递增栈。
1.2 单调递减栈
单调递减栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。
这样就保证了：栈中保留的都是比当前入栈元素小的值，并且从栈顶到栈底的元素值是单调递减的。
单调递减栈的入栈、出栈的过程：
- 假设当前进栈元素为 x，如果栈顶元素大于 x，则直接入栈。
- 否则从栈顶开始遍历栈中元素，把大于 x 或者等于 x 的元素弹出栈，直到遇到一个小于 x 的元素为止，然后再把 x 压入栈中。
实例：
-
数组元素：[4, 3, 2, 5, 7, 4, 6, 8]，遍历顺序为从左到右。
image.png
image.png
最终栈中元素为 [2, 4, 6, 8]。因为从栈顶（右端）到栈底（左侧）元素的顺序为 8, 6, 4, 2，满足递减关系，所以这是一个单调递减栈。
二、单调栈适用场景
单调栈可以在时间复杂度为 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。
所以单调栈一般用于解决一下几种问题：
- 寻找左侧第一个比当前元素大的元素
- 寻找左侧第一个比当前元素小的元素
- 寻找右侧第一个比当前元素大的元素
- 寻找右侧第一个比当前元素小的元素
2.1 寻找左侧第一个比当前元素大的元素
从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：一个元素左侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。如果插入时的栈为空，则说明左侧不存在比当前元素大的元素。
2.2 寻找左侧第一个比当前元素小的元素
从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：一个元素左侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。如果插入时的栈为空，则说明左侧不存在比当前元素小的元素。
2.3 寻找右侧第一个比当前元素大的元素
从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：一个元素右侧第一个比它大的元素就是将其「弹出单调递增栈」时即将插入的元素。如果该元素没有被弹出栈，则说明右侧不存在比当前元素大的元素。
从右到左遍历元素，构造单调递增栈（从栈顶到栈底递增）：一个元素左侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。如果插入时的栈为空，则说明左侧不存在比当前元素大的元素。
2.4 寻找右侧第一个比当前元素小的元素
从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：一个元素右侧第一个比它小的元素就是将其「弹出单调递减栈」时即将插入的元素。如果该元素没有被弹出栈，则说明右侧不存在比当前元素小的元素。
从右到左遍历元素，构造单调递减栈（从栈顶到栈底递减）：一个元素右侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。如果插入时的栈为空，则说明右侧不存在比当前元素小的元素。
小结
- 无论哪种题型，都建议从左到右遍历元素。
- 查找 「比当前元素大的元素」 就用 单调递增栈，查找「比当前元素小的元素」就用 单调递减栈。
- 从 「左侧」 查找就看 「插入栈」 时的栈顶元素，从 「右侧」 查找就看 「弹出栈」 时即将插入的元素。
三、单调栈模板
3.1 单调递增栈模板
def monotoneIncreasingStack(nums):
stack = []
for num in nums:
while stack and num >= stack[-1]:
stack.pop()
stack.append(num)
3.2 单调递减栈模板
def monotoneDecreasingStack(nums):
stack = []
for num in nums:
while stack and num <= stack[-1]:
stack.pop()
stack.append(num)
四、单调栈的应用
下一个更大元素、每日温度等。
五、总结
本章节主要介绍了单调栈的类型、基础理论、实现过程和使用场景。单调栈原理很简单，就是按大小排成一列，但是不能小觑，它的操作不能一步到位，只能一步一步实现，而且不一定所有的数都能入栈，有些数可能被弹出去不能入栈。
