[TOC]
单调栈
适用范围：题目涉及到下（上）一个更大（小）元素
(e.g. Leetcode739) 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
可以从左看和从右看。
从左边看，需要一个单调递减栈。栈里面储存元素是待寻找下一个更大值的元素（的index）。
从右边看，需要一个单调递减栈。遍历的元素是待寻找下一个更大值的元素（的index），栈里面的只是milestone。
及时去掉无用（之后遍历中不会用到的）数据，保证栈中数据有序。
- 从左向右写法
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0]*n
st = []
for i in range(0,n):
while st and temperatures[st[-1]]<temperatures[i]:
ans[st.pop()]=i-st[-1]
st.append(i)
return ans
- 从右向左写法
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0]*n
st = []
for i in range(n-1,-1,-1):
while st and temperatures[st[-1]]<=temperatures[i]:
st.pop()
if st: ans[i] = st[-1]-i
st.append(i)
return ans
Leetcode 题单
单调栈
- 商品折扣后的最终价格
- 下一个更大元素 I
- 下一个更大元素 II
- 链表中的下一个更大节点 1571
- 股票价格跨度 1709
- 表现良好的最长时间段 1908
- 132 模式 ~2000
- 美丽塔 II 2072
- 下一个更大元素 IV 2175
- 使数组按非递减顺序排列 2482
- 每个元素为最大值的最大范围（会员题） 矩形系列
- 柱状图中最大的矩形
- 最大矩形
- 统计全 1 子矩形 1845 字典序最小
- 去除重复字母 316 扩展：重复个数不超过 limit
- 移掉 K 位数字 ~1800
- 找出最具竞争力的子序列 1802
- 拼接最大数 贡献法（计算所有子数组的……的和）
- 子数组的最小值之和 1976
- 子数组范围和（最大值-最小值） O(n)\mathcal{O}(n)O(n) 做法 ~2000
- 子数组最小乘积的最大值 2051
- 操作使得分最大 2397
- 巫师的总力量和（最小值*和） 2621
