**单调栈:** 1. 保证栈内元素的单调性( '从栈底到栈顶' 或递增 或递减 ) 2. 保证单调性的基准是什么 栈内放入的元素是什么( 本题利用温度保持单调性 将下标存入栈中 ) ```python class Solution: # 给定一个整数数组temperatures，表示每天的温度，返回一个数组answer， # 其中answer[i]是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 # 示例: # 输入: temperatures = [73,74,75,71,69,72,76,73] # 输出: [1,1,4,2,1,1,0,0] def dailyTemperatures(self, temperatures: List[int]) -> List[int]: # 单调栈: # 1. 保证栈内元素的单调性( '从栈底到栈顶' 或递增 或递减 ) # 2. 保证单调性的基准是什么 栈内放入的元素是什么( 本题利用温度保持单调性 将下标存入栈中 ) # 下一个更高温度出现在几天后 # 保证栈中温度从'栈底到栈顶'是递增的 为了方便确定几天后 栈顶存储下标 n = len( temperatures ) st = [] ans = [ 0 for _ in range( n ) ] for i, v in enumerate( temperatures ): while st and v > temperatures[ st[ -1 ] ]: # 保证栈内没有比栈顶温度小的元素 idx = st.pop() ans[ idx ] = i - idx st.append( i ) return ans ``` ## 单调栈详解 ``` 单调栈能够解决的问题 单调栈（Monotonic Stack）是一种栈内元素保持单调递增或单调递减的栈结构。 它在遍历元素时，能够高效地找到每个元素"左/右侧第一个比它大/小"的元素。 时间复杂度通常为 O(n)，常用于替代暴力双层循环。 ═══════════════════════════════════════════ 一、核心能解决的问题 ═══════════════════════════════════════════ 1. 下一个更大元素 / 下一个更小元素 - 找每个元素右侧第一个比它大的元素（Next Greater Element） - 找每个元素右侧第一个比它小的元素（Next Smaller Element） - 同理也可以找左侧 2. 上一个更大元素 / 上一个更小元素 - 找每个元素左侧第一个比它大的元素（Previous Greater Element） - 找每个元素左侧第一个比它小的元素（Previous Smaller Element） 3. 区间最值相关 - 以某个元素为最值的最大区间范围（如柱状图中最大矩形） - 每个元素作为最值的影响范围 4. 括号匹配与表达式求值 - 验证括号是否有效 - 表达式的解析与计算 ═══════════════════════════════════════════ 二、经典题目分类 ═══════════════════════════════════════════ 【类型 A：下一个/上一个 更大/更小 元素】 LeetCode 496 - 下一个更大元素 I （模板题） LeetCode 503 - 下一个更大元素 II （循环数组） LeetCode 556 - 下一个更大元素 III （下一个排列） LeetCode 739 - 每日温度 （找右侧第一个更大的距离） LeetCode 901 - 股票价格跨度 （左侧第一个更大的距离） 【类型 B：柱状图/矩形面积】 LeetCode 84 - 柱状图中最大的矩形 （最经典，左右第一个更小元素） LeetCode 85 - 最大矩形 （二维扩展） LeetCode 42 - 接雨水 （两侧最大值，单调栈/双指针） LeetCode 1856 - 子数组最小乘积的最大值 （以某元素为最小值的区间） 【类型 C：字典序/排列】 LeetCode 316 - 去除重复字母 （单调栈保证字典序） LeetCode 1081 - 不同字符的最小子序列 （同上） LeetCode 402 - 移掉 K 位数字 （单调栈找最小数字） LeetCode 321 - 拼接最大数 （两个序列单调栈合并） 【类型 D：表达式与括号】 LeetCode 20 - 有效的括号 LeetCode 32 - 最长有效括号 LeetCode 150 - 逆波兰表达式求值 LeetCode 224 - 基本计算器 LeetCode 227 - 基本计算器 II LeetCode 772 - 基本计算器 III 【类型 E：其他进阶】 LeetCode 907 - 子数组的最小值之和 LeetCode 2104 - 子数组范围和 LeetCode 2281 - 巫师的总力量和 LeetCode 2289 - 使数组按非递减顺序排列的步骤数 ═══════════════════════════════════════════ 三、单调栈的基本模板 ═══════════════════════════════════════════ 1. 找右侧第一个更大的元素（递增栈） stack = [] for i in range(n): while stack and nums[stack[-1]] < nums[i]: idx = stack.pop() result[idx] = nums[i] # 或 i - idx stack.append(i) 2. 找右侧第一个更小的元素（递减栈） stack = [] for i in range(n): while stack and nums[stack[-1]] > nums[i]: idx = stack.pop() result[idx] = nums[i] stack.append(i) 3. 循环数组版本 遍历两遍，下标取模即可 for i in range(2 * n): while stack and nums[stack[-1]] < nums[i % n]: ... ═══════════════════════════════════════════ 四、单调栈的核心思想 ═══════════════════════════════════════════ - 当前元素破坏了栈的单调性时，就弹出栈顶， 此时： · 弹出的元素 = 找到了它要的结果 · 当前元素 = 结果的值 - 遍历完后栈中剩余的元素，就是没有找到结果的元素。 - 单调栈本质上是用空间换时间， 将"对每个元素找左/右第一个更大/更小"从 O(n²) 降到 O(n)。 ```