单调栈
知识点理解
将栈中的元素按单调的顺序排列，以满足题目要求。那怎么令其按照单调顺序排列呢？就是每新来一个元素都和栈顶元素比较，如果不满足要求，就出栈。
- 保持栈递增或者递减
- 将栈顶元素和当前元素做一些操作，放到res中
- 把当前元素放入栈中
最大的优势是时间复杂度是线性的，每个元素只遍历一次。
时间复杂度为O(n)，nums 中的每一个元素最多被入栈一次及出栈一次，没有任何多余的操作
适用于寻找下一个更大元素or上一个更小元素这类题目.
题目84最为经典.既要寻找下一个较小元素,又要寻找上一个较小元素.
经常和动态规划结合在一起.此时,遍历数组时,栈顶元素的被看做的常规意义下的当前元素
模板
class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: res = {} stack = [] for i in range(len(nums2)-1, -1, -1): #1. 保持栈递减（实际其实不需要明确知道递增还是递减，只需要知道栈顶的是这次需要放入结果的） while stack and stack[-1] < nums2[i]: stack.pop() #2. 将栈顶放入结果 res[nums2[i]] = stack[-1] if stack else -1 #3. 当前元素入栈 stack.append(nums2[i]) return [res[i] for i in nums1]
经典题目
找单边小于 or 大于自身的下标
找左右双边都小于自身的下标
这类题目需要知道某个范围的最小值，且需要知道该范围的左右边界！知道左右边界后，那么该子数组的最小值也就知道了。或者说该最小值作为多少个 子数组的最小值也就知道了，见2104。
移除字母——构造字典序
思路：利用单调栈构造递增 or 递减序列，单调栈弹出的即为移除的字母，最后答案就是stack中的字符。
栈结构设计题
子数组元素数量个数
子数组数量，考虑以某个元素下标
i为起点，计算满足条件的终点下标j，那么以i为起点的子数组数量为 j-i+1。这类题目不管是滑动窗口还是单调栈均是如此！技巧题
本质上还属于上述几种类型的扩展。
单调栈 通常用于寻找比当前元素大 or 小的元素，都在站在当前字符的位置看的。