1. 从“排队”到“解题”为什么单调栈是算法面试的常客如果你刷过LeetCode或者准备过技术面试大概率在“下一个更大元素”、“柱状图中最大矩形”、“每日温度”这类题目里见过它的身影。单调栈Monotonic Stack这个名字听起来有点学术但它的核心思想却异常生活化。想象一下你在食堂排队打饭队伍总是按照身高从矮到高排列单调递增这时来了一个更高的人他需要站到队伍中合适的位置以保证队伍依然有序。这个“维持队伍有序性”的过程就是单调栈最直观的体现。在算法领域单调栈是一种特殊的栈数据结构它要求栈中的元素通常是它们的索引或值始终保持单调性——要么单调递增要么单调递减。它的威力在于能以O(n)的时间复杂度高效解决一类“寻找每个元素左/右侧第一个比它大或小的元素”的问题。这类问题如果暴力求解复杂度往往是 O(n²)在数据量稍大时就会捉襟见肘。因此单调栈成了优化这类问题的“标准答案”也是区分普通程序员和算法高手的一道分水岭。我最初接触单调栈时觉得它像是一个“记忆工具”。它不会忘记之前遍历过的元素但只记住那些“有可能成为未来答案”的关键元素把那些已经确定无用的元素果断抛弃。这种“选择性记忆”的智慧正是其高效的本质。接下来我们不谈空泛的理论直接深入到它的工作原理、经典应用以及那些容易踩坑的细节里让你真正掌握这把利器。2. 单调栈的核心工作原理它到底是如何“选择记忆”的理解单调栈关键在于理解它的“入栈”和“出栈”规则。这个规则由我们想要解决的问题的单调性方向决定。我们通过一个最经典的问题来拆解这个过程“下一个更大元素 I”。题目通常描述为给定一个数组 nums返回一个等长的数组 answer其中 answer[i] 是 nums[i] 右侧第一个比它大的元素如果不存在则设为 -1。例如对于数组[2, 1, 2, 4, 3]我们期望的结果是[4, 2, 4, -1, -1]。2.1 单调递减栈的运作流程对于“寻找右侧第一个更大元素”的问题我们通常维护一个单调递减栈从栈底到栈顶元素值递减。栈里存放的是元素的索引这样便于我们定位和赋值。我们来一步步模拟假设栈为stack初始为空从左到右遍历数组索引0值2栈空直接入栈。stack [0]。当前元素2还没有找到它的“下一个更大元素”暂时等待。索引1值1比较当前值1和栈顶索引对应的值nums[stack[-1]] 2。因为1 2满足递减趋势直接入栈。stack [0, 1]。索引2值2当前值2与栈顶值nums[1]1比较。2 1破坏了栈的单调递减性。这是一个关键信号对于栈顶元素索引1值1来说当前遍历到的元素2就是它右侧第一个比它大的元素于是我们弹出栈顶元素索引1并为answer[1]赋值为当前元素2。此时栈顶变为索引0值为2。继续比较2 2不满足“大于”条件因此当前元素2入栈。stack [0, 2]。answer [?, 2, ?, ?, ?]。索引3值4当前值4与栈顶值nums[2]2比较。4 2再次破坏单调性。弹出栈顶索引2设置answer[2] 4。栈顶变为索引0值为2。继续比较4 2再次破坏单调性。弹出栈顶索引0设置answer[0] 4。栈空当前元素4入栈。stack [3]。answer [4, 2, 4, ?, ?]。索引4值3当前值3与栈顶值nums[3]4比较。3 4满足递减趋势直接入栈。stack [3, 4]。遍历结束。收尾工作遍历结束后栈中还有元素[3, 4]。这意味着对于索引3和4的元素在它们的右侧都没有找到更大的元素。因此将answer[3]和answer[4]设为 -1。最终answer [4, 2, 4, -1, -1]。注意很多初学者会混淆“单调栈”是递增还是递减。一个简单的记忆口诀是找“更大”用“递减栈”因为遇到更大的就要清算栈里小的找“更小”用“递增栈”因为遇到更小的就要清算栈里大的。栈的单调方向与我们要寻找的目标方向相反。2.2 空间与时间复杂度分析时间复杂度 O(n)每个元素最多入栈一次、出栈一次总操作次数约为 2n因此是线性复杂度。空间复杂度 O(n)最坏情况下数组本身单调递减所有元素都会入栈栈空间使用为 n。这个“每个元素一进一出”的特性是单调栈高效的核心。它避免了像暴力法那样对每个元素都向后扫描整个数组的冗余操作。3. 单调栈的四大经典应用场景与变体掌握了基本模型我们来看看单调栈能解决哪些具体问题。这些问题往往有固定的“解题模板”但细微之处见真章。3.1 场景一相邻关系问题Next Greater Element这就是我们上面详解的经典问题。它有几个直接的变体下一个更小元素只需将单调递减栈改为单调递增栈比较逻辑从改为。前一个更大/更小元素只需将遍历方向从“从左到右”改为“从右到左”逻辑完全不变。因为“左侧第一个”等价于“从右向左遍历时的右侧第一个”。代码模板下一个更大元素单调递减栈def nextGreaterElement(nums): n len(nums) answer [-1] * n stack [] # 存储索引单调递减 for i in range(n): # 当栈不为空且当前元素大于栈顶元素时进行清算 while stack and nums[i] nums[stack[-1]]: idx stack.pop() answer[idx] nums[i] stack.append(i) # 遍历结束后栈中剩余元素的答案默认为-1初始化时已设置 return answer3.2 场景二边界确定问题Largest Rectangle in Histogram这是LeetCode上的一道Hard题但用单调栈思路非常清晰。问题给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1。求在该柱状图中能够勾勒出来的最大矩形的面积。暴力法的困境对于每个柱子我们试图以它的高度作为矩形的高度然后向左右两边扩展直到遇到比它矮的柱子。这需要 O(n²) 的时间。单调栈的妙用我们可以维护一个单调递增栈。当遇到一个比栈顶柱子矮的柱子时对于栈顶柱子而言当前柱子的索引就是它右边第一个比它矮的边界。那么它的左边界呢就是它在栈中的下一个元素因为栈是递增的下一个元素肯定比它矮或者是栈底。这样在一次遍历中我们就能确定每个柱子作为高时的最大宽度。关键步骤在数组前后各加入一个高度为0的哨兵柱子方便处理边界情况栈不会空且最终所有有效柱子都会出栈。遍历柱子高度数组。维护单调递增栈存储索引。当当前高度小于栈顶高度时弹出栈顶元素h其高度为height[h]。此时新的栈顶元素stack[-1]是左边界当前遍历索引i是右边界。宽度为i - stack[-1] - 1。计算面积height[h] * width并更新最大值。这个例子深刻展示了单调栈如何同时确定左右两个边界是应用的一次升华。3.3 场景三维护最值问题Sliding Window Maximum虽然滑动窗口最大值最经典的解法是使用双端队列Deque但其思想与单调栈确切地说是单调队列同源。我们需要维护一个窗口内的元素索引并保证队列头部永远是当前窗口最大值的索引且队列中的元素值从头部到尾部是递减的。当窗口滑动时移除队头过期索引超出窗口范围的元素。将新元素从队尾开始比较弹出所有比它小的元素索引因为它们不可能再成为未来窗口的最大值了然后加入新索引。队头索引对应的值就是当前窗口的最大值。这本质上是一个既能从头部也能从尾部操作的“单调栈”它维护的是“可能成为未来窗口最大值”的候选元素。3.4 场景四跨度类问题Daily Temperatures问题给定一个温度列表返回一个列表表示需要等待多少天才能等到更暖和的温度。如果未来都不会更暖和则用0表示。例如输入[73,74,75,71,69,72,76,73]输出[1,1,4,2,1,1,0,0]。分析这完全是“下一个更大元素”问题的变体。只不过答案从“值”变成了“索引的差值”天数。我们依然使用单调递减栈当弹出栈顶元素时i - stack.pop()就是需要等待的天数。代码差异点def dailyTemperatures(temperatures): n len(temperatures) answer [0] * n stack [] # 存储索引 for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() answer[idx] i - idx # 计算天数差 stack.append(i) return answer4. 从原理到实现构建你自己的单调栈解题框架经过多个场景的洗礼我们可以总结出一套适用于大多数单调栈问题的思考与实现框架。这套框架能帮助你在遇到新问题时快速定位解法。4.1 四步决策法面对一个问题判断是否能用单调栈以及如何用可以遵循以下四步问题转化明确问题是否在寻找每个元素的“左/右侧第一个大于/小于它的元素”或“边界”。如果是优先考虑单调栈。确定单调性找右侧第一个更大-单调递减栈栈顶最小。找右侧第一个更小-单调递增栈栈顶最大。找左侧第一个更大-从右向左遍历单调递减栈。找左侧第一个更小-从右向左遍历单调递增栈。确定存储内容栈里存什么绝大多数情况存索引便于计算距离、宽度和赋值。少数只关心值本身的问题可以存值。设计清算逻辑在循环中当“当前元素”破坏栈的单调性时触发清算。弹出栈顶元素此时“当前元素”就是被弹出元素的“目标答案”第一个更大/更小元素。根据问题计算具体答案值、索引差、面积等。4.2 通用代码模板与注释以下是一个寻找“右侧第一个更大元素”的增强版模板包含了详细的注释和调试信息点。def monotonicStackTemplate(nums): n len(nums) # 初始化答案数组通常用-1、0或None填充 res [-1] * n # 初始化栈存放元素索引 stack [] for i in range(n): current_value nums[i] # 核心当栈不空且当前元素破坏单调性时进行清算 # 这里是“递减栈”找“更大”所以条件是 current_value nums[stack[-1]] # 如果是“递增栈”找“更小”则条件应为 current_value nums[stack[-1]] while stack and current_value nums[stack[-1]]: # 弹出栈顶元素它找到了它的“下一个更大元素” top_index stack.pop() # 根据问题计算答案。这里是直接赋值当前值。 res[top_index] current_value # 调试时可以打印print(f元素 {nums[top_index]} (索引{top_index}) 的下一个更大元素是 {current_value} (索引{i})) # 清算完成后当前元素入栈等待它自己的“下一个更大元素” stack.append(i) # 遍历结束后栈中剩余的元素意味着在右侧没有找到更大的元素。 # 我们的答案数组在初始化时已经设置了默认值如-1所以这里通常不需要额外操作。 # 但有些问题如柱状图最大矩形需要特殊处理栈内剩余元素。 return res4.3 边界条件与初始化技巧这是最容易出错的地方。空栈判断在while循环中必须先判断stack是否为空再访问stack[-1]否则会引发索引错误。相等元素的处理这是单调栈的一个关键细节。在“下一个更大元素”问题中如果遇到相等的元素怎么办根据问题定义“第一个大于”通常不包含等于。所以当current_value nums[stack[-1]]时不触发清算直接入栈。这保证了栈是严格单调的。但在某些变体问题中可能需要考虑相等的情况务必审题。哨兵技巧Sentinel在“柱状图最大矩形”等问题中在数组头尾添加高度为0的哨兵可以极大地简化代码逻辑避免在循环外再写一段处理栈内剩余元素的代码。这是一个非常实用的优化技巧。答案数组初始化根据问题合理初始化res数组。找“下一个更大”通常用-1计算“天数”用0。5. 实战进阶破解“接雨水”与“最大矩形”难题理解了框架我们挑战两个更综合的题目看看单调栈如何与其他思想结合。5.1 LeetCode 42. 接雨水这是单调栈的经典应用题。问题给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。单调栈解法思路 我们可以按行来计算雨水。维护一个单调递减栈存储索引来跟踪可能储水的最左边界。遍历高度数组。当当前高度大于栈顶高度时说明可能形成了一个凹槽。弹出栈顶元素作为凹槽的底部bottom。如果此时栈不空新的栈顶元素left是左边界当前索引i是右边界。雨水的宽度是i - left - 1。雨水的高度是min(height[left], height[i]) - height[bottom]左右边界较矮者减去底部高度。积水量 width * height。这个解法的精妙之处在于每次计算的是当前遍历到的柱子右边界和栈顶的下一个柱子左边界之间以弹出柱子为底的那一层水。它通过单调栈自然找到了每个凹槽的左右边界。5.2 LeetCode 85. 最大矩形问题给定一个仅包含0和1的二维二进制矩阵找出只包含1的最大矩形并返回其面积。解法思路此题可以巧妙地转化为多个“柱状图中最大矩形”问题。对于矩阵的每一行我们可以计算一个heights数组其中heights[j]表示从当前行开始向上连续1的个数即以此行为底第j列柱子的高度。对每一行计算得到的heights数组调用“柱状图中最大矩形”的单调栈解法。所有行结果中的最大值就是整个矩阵的最大矩形面积。例如矩阵[[1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0]]第一行heights [1,0,1,0,0]第二行heights [2,0,2,1,1]遇到0则重置为0遇到1则累加 第三行heights [3,1,3,2,2]第四行heights [4,0,0,3,0]然后对每一行的heights应用单调栈求最大矩形。这个方法将二维问题降维到了一维是单调栈结合动态规划思想的典范。6. 避坑指南与性能优化来自实战的经验之谈理论很美好但一写就错。下面分享几个我踩过的坑和总结的优化点。6.1 常见错误与调试方法单调性方向搞反这是最最常见的错误。再次强调口诀找更大用递减栈找更小用递增栈。如果不确定就拿一个简单例子如[2,1,3]在纸上画一遍流程。索引与值的混淆栈里存的是索引但比较和赋值时容易直接拿索引当值用。务必清楚stack[-1]是索引nums[stack[-1]]才是值。循环结束后栈内元素未处理在“下一个更大元素”问题中栈内剩余元素对应答案就是-1初始化已解决。但在“柱状图最大矩形”中必须在循环结束后主动处理栈内剩余元素或者使用哨兵技巧避免。宽度计算错误在计算矩形宽度时容易写成i - bottom_index正确的应该是i - left_index - 1其中left_index是弹出底部索引后的新栈顶。这里的-1是因为左右边界都不包含底部柱子本身。调试技巧在while循环内部和每次入栈后打印出当前的栈状态索引和对应的值以及答案数组是理解流程最快的方式。6.2 空间与时间的极致优化单调栈本身已经是 O(n) 时间复杂度的优化算法了但在某些场景下还有微调空间原地修改数组作为栈在一些内存限制极严格或追求极致性能的场景如某些嵌入式环境或竞赛如果不需要保留原数组可以考虑用原数组的前面部分作为栈空间用一个指针top来模拟栈顶。这可以将空间复杂度从 O(n) 降低到 O(1)如果不算输出数组的话。但会破坏输入数据且代码可读性变差日常开发不推荐。避免重复计算在“接雨水”问题中计算高度min(height[left], height[i]) - height[bottom]时height[bottom]在弹出时已经知道可以存储起来避免重复访问数组。选择合适的数据结构在Python中list作为栈已经非常高效。在Java中ArrayDeque比Stack类性能更好。在C中直接用vector或deque。6.3 何时选择单调栈与其他算法的对比单调栈不是万能的要识别它的适用场景VS 暴力法当暴力解法是 O(n²) 的双重循环且内层循环在寻找边界时单调栈几乎总是更优解。VS 动态规划有些问题既可以用DP也可以用单调栈如“最长有效括号”的某些解法。DP通常状态定义更复杂但思维模式更通用单调栈针对性强代码简洁。如果问题有明显的“最近相关性”答案只与最近的几个元素有关单调栈可能更直观。VS 分治法例如“最大矩形”问题也可以用分治如基于线段树但实现复杂。单调栈解法在面试和实践中更受欢迎。一个简单的判断标准如果问题描述中出现了“第一个”、“最近的”、“最大的”、“最小的”这类字眼并且需要为每个元素都找一个这样的对应关系那么就该立刻想到单调栈。7. 思维延伸单调栈在复杂系统中的设计启示单调栈的价值不止于解算法题。它的设计思想——“维护一个有序的候选集及时剔除无效元素高效找到目标”——在软件系统设计中也有体现。缓存淘汰策略如LRU虽然LRU通常用哈希表加双向链表实现但其核心思想也是维护一个“最近使用”的序列淘汰最久未使用的。这与单调栈“维护有序并剔除”的思想有相通之处。任务调度在某些调度器中可能需要维护一个按优先级或截止时间排序的任务队列。当新任务到来时需要快速定位其位置或淘汰掉某些不可能执行的任务这个过程就类似一个动态的“单调队列”。实时数据流中的统计例如在一个持续的数据流中需要快速获取当前中位数或某百分位数。使用两个堆大顶堆和小顶堆来维护其“保持堆顶元素为关键值”的思想与单调栈维护栈顶元素为关键边界的思想同源。理解一个数据结构或算法最高境界是理解其抽象出来的思维模型。单调栈的模型就是在面对一个序列时如何通过维护一个简化的、有序的视图来避免重复遍历从而高效地回答关于序列中元素间关系的问题。掌握了这个模型你就能在更广阔的领域识别出类似的问题并应用相应的优化策略。从我个人的经验来看学习单调栈最好的方法不是死记模板而是亲手推导几个经典例子的完整过程理解每一次入栈和出栈背后的“为什么”。然后尝试用这个思维去解新的题目即使一开始会卡壳但思考的过程本身就是最好的训练。当你能够不假思索地判断出一道题该用递增栈还是递减栈该存索引还是存值时你就真正掌握了它。算法学习很多时候就是这样一个从“形似”到“神似”的过程。
1. 从“排队”到“解题”为什么单调栈是算法面试的常客如果你刷过LeetCode或者准备过技术面试大概率在“下一个更大元素”、“柱状图中最大矩形”、“每日温度”这类题目里见过它的身影。单调栈Monotonic Stack这个名字听起来有点学术但它的核心思想却异常生活化。想象一下你在食堂排队打饭队伍总是按照身高从矮到高排列单调递增这时来了一个更高的人他需要站到队伍中合适的位置以保证队伍依然有序。这个“维持队伍有序性”的过程就是单调栈最直观的体现。在算法领域单调栈是一种特殊的栈数据结构它要求栈中的元素通常是它们的索引或值始终保持单调性——要么单调递增要么单调递减。它的威力在于能以O(n)的时间复杂度高效解决一类“寻找每个元素左/右侧第一个比它大或小的元素”的问题。这类问题如果暴力求解复杂度往往是 O(n²)在数据量稍大时就会捉襟见肘。因此单调栈成了优化这类问题的“标准答案”也是区分普通程序员和算法高手的一道分水岭。我最初接触单调栈时觉得它像是一个“记忆工具”。它不会忘记之前遍历过的元素但只记住那些“有可能成为未来答案”的关键元素把那些已经确定无用的元素果断抛弃。这种“选择性记忆”的智慧正是其高效的本质。接下来我们不谈空泛的理论直接深入到它的工作原理、经典应用以及那些容易踩坑的细节里让你真正掌握这把利器。2. 单调栈的核心工作原理它到底是如何“选择记忆”的理解单调栈关键在于理解它的“入栈”和“出栈”规则。这个规则由我们想要解决的问题的单调性方向决定。我们通过一个最经典的问题来拆解这个过程“下一个更大元素 I”。题目通常描述为给定一个数组 nums返回一个等长的数组 answer其中 answer[i] 是 nums[i] 右侧第一个比它大的元素如果不存在则设为 -1。例如对于数组[2, 1, 2, 4, 3]我们期望的结果是[4, 2, 4, -1, -1]。2.1 单调递减栈的运作流程对于“寻找右侧第一个更大元素”的问题我们通常维护一个单调递减栈从栈底到栈顶元素值递减。栈里存放的是元素的索引这样便于我们定位和赋值。我们来一步步模拟假设栈为stack初始为空从左到右遍历数组索引0值2栈空直接入栈。stack [0]。当前元素2还没有找到它的“下一个更大元素”暂时等待。索引1值1比较当前值1和栈顶索引对应的值nums[stack[-1]] 2。因为1 2满足递减趋势直接入栈。stack [0, 1]。索引2值2当前值2与栈顶值nums[1]1比较。2 1破坏了栈的单调递减性。这是一个关键信号对于栈顶元素索引1值1来说当前遍历到的元素2就是它右侧第一个比它大的元素于是我们弹出栈顶元素索引1并为answer[1]赋值为当前元素2。此时栈顶变为索引0值为2。继续比较2 2不满足“大于”条件因此当前元素2入栈。stack [0, 2]。answer [?, 2, ?, ?, ?]。索引3值4当前值4与栈顶值nums[2]2比较。4 2再次破坏单调性。弹出栈顶索引2设置answer[2] 4。栈顶变为索引0值为2。继续比较4 2再次破坏单调性。弹出栈顶索引0设置answer[0] 4。栈空当前元素4入栈。stack [3]。answer [4, 2, 4, ?, ?]。索引4值3当前值3与栈顶值nums[3]4比较。3 4满足递减趋势直接入栈。stack [3, 4]。遍历结束。收尾工作遍历结束后栈中还有元素[3, 4]。这意味着对于索引3和4的元素在它们的右侧都没有找到更大的元素。因此将answer[3]和answer[4]设为 -1。最终answer [4, 2, 4, -1, -1]。注意很多初学者会混淆“单调栈”是递增还是递减。一个简单的记忆口诀是找“更大”用“递减栈”因为遇到更大的就要清算栈里小的找“更小”用“递增栈”因为遇到更小的就要清算栈里大的。栈的单调方向与我们要寻找的目标方向相反。2.2 空间与时间复杂度分析时间复杂度 O(n)每个元素最多入栈一次、出栈一次总操作次数约为 2n因此是线性复杂度。空间复杂度 O(n)最坏情况下数组本身单调递减所有元素都会入栈栈空间使用为 n。这个“每个元素一进一出”的特性是单调栈高效的核心。它避免了像暴力法那样对每个元素都向后扫描整个数组的冗余操作。3. 单调栈的四大经典应用场景与变体掌握了基本模型我们来看看单调栈能解决哪些具体问题。这些问题往往有固定的“解题模板”但细微之处见真章。3.1 场景一相邻关系问题Next Greater Element这就是我们上面详解的经典问题。它有几个直接的变体下一个更小元素只需将单调递减栈改为单调递增栈比较逻辑从改为。前一个更大/更小元素只需将遍历方向从“从左到右”改为“从右到左”逻辑完全不变。因为“左侧第一个”等价于“从右向左遍历时的右侧第一个”。代码模板下一个更大元素单调递减栈def nextGreaterElement(nums): n len(nums) answer [-1] * n stack [] # 存储索引单调递减 for i in range(n): # 当栈不为空且当前元素大于栈顶元素时进行清算 while stack and nums[i] nums[stack[-1]]: idx stack.pop() answer[idx] nums[i] stack.append(i) # 遍历结束后栈中剩余元素的答案默认为-1初始化时已设置 return answer3.2 场景二边界确定问题Largest Rectangle in Histogram这是LeetCode上的一道Hard题但用单调栈思路非常清晰。问题给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1。求在该柱状图中能够勾勒出来的最大矩形的面积。暴力法的困境对于每个柱子我们试图以它的高度作为矩形的高度然后向左右两边扩展直到遇到比它矮的柱子。这需要 O(n²) 的时间。单调栈的妙用我们可以维护一个单调递增栈。当遇到一个比栈顶柱子矮的柱子时对于栈顶柱子而言当前柱子的索引就是它右边第一个比它矮的边界。那么它的左边界呢就是它在栈中的下一个元素因为栈是递增的下一个元素肯定比它矮或者是栈底。这样在一次遍历中我们就能确定每个柱子作为高时的最大宽度。关键步骤在数组前后各加入一个高度为0的哨兵柱子方便处理边界情况栈不会空且最终所有有效柱子都会出栈。遍历柱子高度数组。维护单调递增栈存储索引。当当前高度小于栈顶高度时弹出栈顶元素h其高度为height[h]。此时新的栈顶元素stack[-1]是左边界当前遍历索引i是右边界。宽度为i - stack[-1] - 1。计算面积height[h] * width并更新最大值。这个例子深刻展示了单调栈如何同时确定左右两个边界是应用的一次升华。3.3 场景三维护最值问题Sliding Window Maximum虽然滑动窗口最大值最经典的解法是使用双端队列Deque但其思想与单调栈确切地说是单调队列同源。我们需要维护一个窗口内的元素索引并保证队列头部永远是当前窗口最大值的索引且队列中的元素值从头部到尾部是递减的。当窗口滑动时移除队头过期索引超出窗口范围的元素。将新元素从队尾开始比较弹出所有比它小的元素索引因为它们不可能再成为未来窗口的最大值了然后加入新索引。队头索引对应的值就是当前窗口的最大值。这本质上是一个既能从头部也能从尾部操作的“单调栈”它维护的是“可能成为未来窗口最大值”的候选元素。3.4 场景四跨度类问题Daily Temperatures问题给定一个温度列表返回一个列表表示需要等待多少天才能等到更暖和的温度。如果未来都不会更暖和则用0表示。例如输入[73,74,75,71,69,72,76,73]输出[1,1,4,2,1,1,0,0]。分析这完全是“下一个更大元素”问题的变体。只不过答案从“值”变成了“索引的差值”天数。我们依然使用单调递减栈当弹出栈顶元素时i - stack.pop()就是需要等待的天数。代码差异点def dailyTemperatures(temperatures): n len(temperatures) answer [0] * n stack [] # 存储索引 for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() answer[idx] i - idx # 计算天数差 stack.append(i) return answer4. 从原理到实现构建你自己的单调栈解题框架经过多个场景的洗礼我们可以总结出一套适用于大多数单调栈问题的思考与实现框架。这套框架能帮助你在遇到新问题时快速定位解法。4.1 四步决策法面对一个问题判断是否能用单调栈以及如何用可以遵循以下四步问题转化明确问题是否在寻找每个元素的“左/右侧第一个大于/小于它的元素”或“边界”。如果是优先考虑单调栈。确定单调性找右侧第一个更大-单调递减栈栈顶最小。找右侧第一个更小-单调递增栈栈顶最大。找左侧第一个更大-从右向左遍历单调递减栈。找左侧第一个更小-从右向左遍历单调递增栈。确定存储内容栈里存什么绝大多数情况存索引便于计算距离、宽度和赋值。少数只关心值本身的问题可以存值。设计清算逻辑在循环中当“当前元素”破坏栈的单调性时触发清算。弹出栈顶元素此时“当前元素”就是被弹出元素的“目标答案”第一个更大/更小元素。根据问题计算具体答案值、索引差、面积等。4.2 通用代码模板与注释以下是一个寻找“右侧第一个更大元素”的增强版模板包含了详细的注释和调试信息点。def monotonicStackTemplate(nums): n len(nums) # 初始化答案数组通常用-1、0或None填充 res [-1] * n # 初始化栈存放元素索引 stack [] for i in range(n): current_value nums[i] # 核心当栈不空且当前元素破坏单调性时进行清算 # 这里是“递减栈”找“更大”所以条件是 current_value nums[stack[-1]] # 如果是“递增栈”找“更小”则条件应为 current_value nums[stack[-1]] while stack and current_value nums[stack[-1]]: # 弹出栈顶元素它找到了它的“下一个更大元素” top_index stack.pop() # 根据问题计算答案。这里是直接赋值当前值。 res[top_index] current_value # 调试时可以打印print(f元素 {nums[top_index]} (索引{top_index}) 的下一个更大元素是 {current_value} (索引{i})) # 清算完成后当前元素入栈等待它自己的“下一个更大元素” stack.append(i) # 遍历结束后栈中剩余的元素意味着在右侧没有找到更大的元素。 # 我们的答案数组在初始化时已经设置了默认值如-1所以这里通常不需要额外操作。 # 但有些问题如柱状图最大矩形需要特殊处理栈内剩余元素。 return res4.3 边界条件与初始化技巧这是最容易出错的地方。空栈判断在while循环中必须先判断stack是否为空再访问stack[-1]否则会引发索引错误。相等元素的处理这是单调栈的一个关键细节。在“下一个更大元素”问题中如果遇到相等的元素怎么办根据问题定义“第一个大于”通常不包含等于。所以当current_value nums[stack[-1]]时不触发清算直接入栈。这保证了栈是严格单调的。但在某些变体问题中可能需要考虑相等的情况务必审题。哨兵技巧Sentinel在“柱状图最大矩形”等问题中在数组头尾添加高度为0的哨兵可以极大地简化代码逻辑避免在循环外再写一段处理栈内剩余元素的代码。这是一个非常实用的优化技巧。答案数组初始化根据问题合理初始化res数组。找“下一个更大”通常用-1计算“天数”用0。5. 实战进阶破解“接雨水”与“最大矩形”难题理解了框架我们挑战两个更综合的题目看看单调栈如何与其他思想结合。5.1 LeetCode 42. 接雨水这是单调栈的经典应用题。问题给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。单调栈解法思路 我们可以按行来计算雨水。维护一个单调递减栈存储索引来跟踪可能储水的最左边界。遍历高度数组。当当前高度大于栈顶高度时说明可能形成了一个凹槽。弹出栈顶元素作为凹槽的底部bottom。如果此时栈不空新的栈顶元素left是左边界当前索引i是右边界。雨水的宽度是i - left - 1。雨水的高度是min(height[left], height[i]) - height[bottom]左右边界较矮者减去底部高度。积水量 width * height。这个解法的精妙之处在于每次计算的是当前遍历到的柱子右边界和栈顶的下一个柱子左边界之间以弹出柱子为底的那一层水。它通过单调栈自然找到了每个凹槽的左右边界。5.2 LeetCode 85. 最大矩形问题给定一个仅包含0和1的二维二进制矩阵找出只包含1的最大矩形并返回其面积。解法思路此题可以巧妙地转化为多个“柱状图中最大矩形”问题。对于矩阵的每一行我们可以计算一个heights数组其中heights[j]表示从当前行开始向上连续1的个数即以此行为底第j列柱子的高度。对每一行计算得到的heights数组调用“柱状图中最大矩形”的单调栈解法。所有行结果中的最大值就是整个矩阵的最大矩形面积。例如矩阵[[1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0]]第一行heights [1,0,1,0,0]第二行heights [2,0,2,1,1]遇到0则重置为0遇到1则累加 第三行heights [3,1,3,2,2]第四行heights [4,0,0,3,0]然后对每一行的heights应用单调栈求最大矩形。这个方法将二维问题降维到了一维是单调栈结合动态规划思想的典范。6. 避坑指南与性能优化来自实战的经验之谈理论很美好但一写就错。下面分享几个我踩过的坑和总结的优化点。6.1 常见错误与调试方法单调性方向搞反这是最最常见的错误。再次强调口诀找更大用递减栈找更小用递增栈。如果不确定就拿一个简单例子如[2,1,3]在纸上画一遍流程。索引与值的混淆栈里存的是索引但比较和赋值时容易直接拿索引当值用。务必清楚stack[-1]是索引nums[stack[-1]]才是值。循环结束后栈内元素未处理在“下一个更大元素”问题中栈内剩余元素对应答案就是-1初始化已解决。但在“柱状图最大矩形”中必须在循环结束后主动处理栈内剩余元素或者使用哨兵技巧避免。宽度计算错误在计算矩形宽度时容易写成i - bottom_index正确的应该是i - left_index - 1其中left_index是弹出底部索引后的新栈顶。这里的-1是因为左右边界都不包含底部柱子本身。调试技巧在while循环内部和每次入栈后打印出当前的栈状态索引和对应的值以及答案数组是理解流程最快的方式。6.2 空间与时间的极致优化单调栈本身已经是 O(n) 时间复杂度的优化算法了但在某些场景下还有微调空间原地修改数组作为栈在一些内存限制极严格或追求极致性能的场景如某些嵌入式环境或竞赛如果不需要保留原数组可以考虑用原数组的前面部分作为栈空间用一个指针top来模拟栈顶。这可以将空间复杂度从 O(n) 降低到 O(1)如果不算输出数组的话。但会破坏输入数据且代码可读性变差日常开发不推荐。避免重复计算在“接雨水”问题中计算高度min(height[left], height[i]) - height[bottom]时height[bottom]在弹出时已经知道可以存储起来避免重复访问数组。选择合适的数据结构在Python中list作为栈已经非常高效。在Java中ArrayDeque比Stack类性能更好。在C中直接用vector或deque。6.3 何时选择单调栈与其他算法的对比单调栈不是万能的要识别它的适用场景VS 暴力法当暴力解法是 O(n²) 的双重循环且内层循环在寻找边界时单调栈几乎总是更优解。VS 动态规划有些问题既可以用DP也可以用单调栈如“最长有效括号”的某些解法。DP通常状态定义更复杂但思维模式更通用单调栈针对性强代码简洁。如果问题有明显的“最近相关性”答案只与最近的几个元素有关单调栈可能更直观。VS 分治法例如“最大矩形”问题也可以用分治如基于线段树但实现复杂。单调栈解法在面试和实践中更受欢迎。一个简单的判断标准如果问题描述中出现了“第一个”、“最近的”、“最大的”、“最小的”这类字眼并且需要为每个元素都找一个这样的对应关系那么就该立刻想到单调栈。7. 思维延伸单调栈在复杂系统中的设计启示单调栈的价值不止于解算法题。它的设计思想——“维护一个有序的候选集及时剔除无效元素高效找到目标”——在软件系统设计中也有体现。缓存淘汰策略如LRU虽然LRU通常用哈希表加双向链表实现但其核心思想也是维护一个“最近使用”的序列淘汰最久未使用的。这与单调栈“维护有序并剔除”的思想有相通之处。任务调度在某些调度器中可能需要维护一个按优先级或截止时间排序的任务队列。当新任务到来时需要快速定位其位置或淘汰掉某些不可能执行的任务这个过程就类似一个动态的“单调队列”。实时数据流中的统计例如在一个持续的数据流中需要快速获取当前中位数或某百分位数。使用两个堆大顶堆和小顶堆来维护其“保持堆顶元素为关键值”的思想与单调栈维护栈顶元素为关键边界的思想同源。理解一个数据结构或算法最高境界是理解其抽象出来的思维模型。单调栈的模型就是在面对一个序列时如何通过维护一个简化的、有序的视图来避免重复遍历从而高效地回答关于序列中元素间关系的问题。掌握了这个模型你就能在更广阔的领域识别出类似的问题并应用相应的优化策略。从我个人的经验来看学习单调栈最好的方法不是死记模板而是亲手推导几个经典例子的完整过程理解每一次入栈和出栈背后的“为什么”。然后尝试用这个思维去解新的题目即使一开始会卡壳但思考的过程本身就是最好的训练。当你能够不假思索地判断出一道题该用递增栈还是递减栈该存索引还是存值时你就真正掌握了它。算法学习很多时候就是这样一个从“形似”到“神似”的过程。
)
