单调栈
介绍
单调栈：满足单调性的栈结构。
过程：
python
[81, 34, 11, 0]
# insert 14
[81, 34, 14] # 依次弹出 0 和 11伪代码：
python
# insert x
while !stk.empty() and stk.top() <= x:
stk.pop()
# stk.top() 为所求
stk.push(x)由于单调栈满足单调性，因此栈顶元素始终满足 它是栈中最小/最大的元素。
举例：
python
[73, 74, 75, 71, 69, 72, 76, 73], =>
stk =
[73] # -1
[73, 74] # 73
[73, 74, 75] # 74
[71] # -1
[69] # -1
[69, 72] # 69
[69, 72, 76] # 72
[69, 72, 73] # 72从左到右遍历，按照 比栈顶大压入，比栈顶小弹出 规则。stk.top() 给出的是每个元素 左边第一个比它小的元素，此时单调栈内是单调递增的（栈底到栈顶）。
python
[73, 74, 75, 71, 69, 72, 76, 73], <=
stk =
[73] # -1
[76] # -1
[76, 72] # 76
[76, 72, 69] # 72
[76, 72, 71] # 72
[76, 75] # 76
[76, 75, 74] # 75
[76, 75, 74, 73] # 74从右往左遍历，按照 比栈顶小压入，比栈顶大弹出 规则。stk.top() 给出的是每个元素 右边第一个比它大的元素，此时单调栈内是单调递减的（栈底到栈顶）。
总结：
- 从左往右遍历，单调递增：左边第一个比它小的元素
- 从左往右遍历，单调递减：左边第一个比它大的元素
- 从右往左遍历，单调递增：右边第一个比它小的元素
- 从右往左遍历，单调递减：右边第一个比它大的元素
另一种思考方式：元素什么时候被弹出，说明此时找到了它的答案，此时再进行赋值（而不是上面所说的 栈顶即答案）。例如：
python
[73, 74, 75, 71, 69, 72, 76, 73], =>
stk =
[73] # -1
[74] # 73 被 74 弹出，因此 73 右边第一个更大的数是 74
[75] # 74 被 75 弹出，因此 74 右边第一个更大的数是 75
[75, 71] # -1
[75, 71, 69] # -1
[75, 72] # 69, 71 均被 72 弹出，说明它们右边第一个更大的数均为 72
[76] # 72, 75 均被 76 弹出，说明它们右边第一个更大的数均为 76
[76, 73] # -1
ans =
[74, 75, 76, 72, 72, 76, -1, -1]伪代码：
python
# insert x
while !stk.empty() and stk.top() < x:
ans[stk.pop()] = x
stk.push(x)需要注意的是 这里不取等号。
- 一个是压入栈时就得到答案
- 一个是弹出栈时才得到答案
模板
查找数组中下一个更大的元素
python
def next_bigger(num: List[int]) -> List[int]:
n = len(nums)
stk = []
for i in range(n - 1, -1, -1):
if len(stk) > 0:参考
题目
力扣题目：
- 739. 每日温度（单调栈模板题）
- 1475. 商品折扣后的最终价格 1212
- 496. 下一个更大元素 I
- 503. 下一个更大元素 II
- 1019. 链表中的下一个更大节点 1571
- 901. 股票价格跨度 1709
- 1124. 表现良好的最长时间段 1908
- 1793. 好子数组的最大分数 1946
- 456. 132 模式 ~2000
- 1944. 队列中可以看到的人数 2105
- 2454. 下一个更大元素 IV 2175
- 2289. 使数组按非递减顺序排列 2482
- 2832. 每个元素为最大值的最大范围（会员题）
洛谷题目：
其他题目：
- 转换 https://codeforces.com/problemset/problem/280/B 1800
- max >= sum https://codeforces.com/problemset/problem/1691/D 1800