1. 单调栈的本质——先搞清楚它在解决什么问题1.1 暴力解法为什么让人头疼先想一个最直观的问题给你一个数组 [2, 1, 4, 3]让你找出每个元素右边第一个比它大的数你会怎么做绝大多数人第一反应是双重循环外层遍历每个元素内层从当前位置往后找遇到第一个更大的就停下。这个思路没有任何问题但内层循环的代价是 O(n)整体复杂度是 O(n²)。数据量小的时候问题不大一旦 n 到了 10⁵ 甚至 10⁶ 的量级双重循环跑起来就是灾难。我在实际刷题中体感最深的是很多题目表面上看是“找某个位置的最近更大值/最近更小值”但只要你开始写双循环基本就掉进了超时的陷阱。这道题真正考察的不是你会不会写循环而是你能不能把“每个元素与它相邻的更大/更小值之间的关系”用一种线性时间的方式统一处理。1.2 单调栈的核心思想单调栈这个名字听着有点唬人说白了就是一种栈栈内元素按照从栈底到栈顶的顺序保持单调递增或单调递减。它解决的问题非常集中给定一个序列快速找到每个元素左边或右边第一个比它大或比它小的元素位置。注意关键词是“第一个”不是“最大”也不是“最小”而是某种比较关系下距离最近的那个边界元素。为了帮助理解我经常用一个生活化的类比想象一个班级里按身高排队每个人想知道离自己最近的前面那个人里第一个比自己高的人是谁。每个人进入队伍的时候如果发现队尾的人比自己矮那队尾的人马上就知道答案了——答案是当前这个比自己高的人然后队尾的人就可以离开队伍。反复执行这个“矮的出队、高的留下”的操作队伍里的人始终是从低到高排的。这就是单调栈的运作模式新元素进来的时候把栈顶那些“不如自己”的元素赶出去因为这些元素在比较关系中已经确定了它们要找的边界。每个元素最多入栈一次、出栈一次所以总时间复杂度是 O(n)。1.3 单调递增栈和单调递减栈怎么选这里有个高频混淆点。很多初学者分不清什么时候用单调递增栈、什么时候用单调递减栈我给出一个非常实用的判断方法要找左边或右边第一个比自己大的元素维护的是从栈底到栈顶单调递减的栈。因为当新元素比栈顶元素大时栈顶立刻找到了“第一个比自己大”的答案。要找左边或右边第一个比自己小的元素维护的是从栈底到栈顶单调递增的栈。因为当新元素比栈顶元素小时栈顶立刻找到了“第一个比自己小”的答案。这个很容易记反。我的记忆方式很简单你要找“大的”那就让“大的”能产生威胁也就是新元素大的时候会触发弹栈你要找“小的”那就让“小的”产生威胁也就是新元素小的时候会触发弹栈。触发弹栈的瞬间就是被弹栈元素得到答案的瞬间。2. 通解的推导——四种情况如何统一成一版代码2.1 问题的完整形式标题里说的“通解”我理解成这样一个完整的问题族给定一个数组 nums要求每个元素左边第一个比它小的元素下标或值每个元素左边第一个比它大的元素每个元素右边第一个比它小的元素每个元素右边第一个比它大的元素这四种情况看起来是四个不同的问题代码也可能四份但从单调栈的角度来看通解只需要一套模板。核心区别只有三点遍历方向从左往右还是从右往左、比较条件什么时候弹栈、记录位置记录左边还是右边。2.2 什么时候更新答案这是整个通解里最关键的判断逻辑。每次新元素 nums[i] 尝试入栈时如果栈顶元素已经“找到了答案”就把栈顶弹出并在弹出的瞬间给栈顶元素的位置设置结果。举个例子我们要找右边第一个比自己大的元素。从左往右遍历当新元素 nums[i] 大于栈顶元素时对于栈顶元素来说nums[i] 就是它右边第一个比它大的值因为我们是顺着数组顺序扫描的第一个遇到的更大的值天然就是“右边第一个”。同理要找右边第一个比自己小的元素从左往右遍历当新元素 nums[i] 小于栈顶元素时栈顶元素就得到了它的答案。那找左边第一个比自己大或者比自己小呢两种思路都行思路一从右往左遍历这样“左边”相对于遍历方向反而变成了“右边”镜像处理。思路二还是从左往右遍历但把答案记录逻辑反过来也就是在扫描过程中维护一个已经见过的元素的单调栈对于每一个新元素栈里存的都是它左边所有还没有找到答案的元素弹出的时机依然受比较条件控制。我实际用下来更推荐“统一从左往右扫描 反向记录”的方案因为这样左右两种情况代码结构完全一致只需要把比较符号换一下、记录方式换一下。2.3 统一模板思路先定义几个变量res结果数组初始化为 -1 或 null表示没找到stack存的是元素下标不是元素值这一点非常重要从左往右遍历 nums对于每个 iwhile 栈不为空 且 当前元素与栈顶元素满足弹栈条件: 栈顶下标 top stack.pop() res[top] i // 记录右侧最近值的位置 stack.push(i)这里“弹栈条件”就是问题的核心开关右侧最近更大值nums[i] nums[stack[-1]]右侧最近更小值nums[i] nums[stack[-1]]如果你要的是左侧最近值有两种处理方式方式一上面的模板得到的是“右侧最近值”然后对这个模板遍历方向反转从右往左得到的就是“左侧最近值”。方式二从左往右遍历当弹出栈顶时栈顶的下一个栈内元素就是栈顶元素左侧最近的候选值。我建议先把右侧的两种情况吃透左侧的用反转遍历方向来镜像解决。这样需要记忆的内容最少不容易出错。3. 从模板到代码——四种变体的具体实现3.1 右侧最近更大值的完整实现先看最经典的“右侧第一个比自己大的元素”。function nextGreaterElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i 0; i n; i) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }这里我特意在res[top]里存的是值有些题目要求存下标那就是res[top] i。建议先统一存下标因为有了下标可以随时取值反过来不行。这个细节看起来不起眼但在追问环节很容易救你一命。有些人会问为什么初始化是 -1因为如果一个元素后面没有更大的数它的结果应该是个特殊标识。用 -1 在竞赛和面试里都是默认做法不用纠结。3.2 右侧最近更小值的实现把比较符号改成小于号就完成了。function nextSmallerElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i 0; i n; i) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }区别只有变成了。这就是通解的力量——你不必把四种情况当作四个独立题目去背只要理解“弹栈瞬间即答案”剩下的都是条件切换。3.3 左侧最近更大值与左侧最近更小值左侧版本我推荐直接反转遍历方向从右往左复用右侧的模板逻辑。function previousGreaterElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i n - 1; i 0; i--) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }注意看代码结构和nextGreaterElement几乎一致只是循环从i 0; i n变成了i n - 1; i 0比较符号不变。因为在“从右往左看”的世界里右侧变成了我们的主扫描方向而被弹出的元素得到的答案就是它在这个反向扫描中遇到的第一个更大值从原数组角度看就是它左侧的最近更大值。同理可得function previousSmallerElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i n - 1; i 0; i--) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }四个函数放在一起看就是两处变量一个循环方向一个比较符号。能用一个模板理解的东西就不要拆成四个知识点来记。3.4 写代码时的三个关键细节第一个细节栈里存的是下标而不是值。为什么因为很多后续题目需要知道位置差、计算宽度、计算面积只有下标才能推导出来。如果只存值位置信息就丢了。第二个细节弹栈之后栈里剩下的元素之间的关系。栈始终保持单调性也就是说当你弹掉若干元素之后新的栈顶一定是当前元素之前最近且满足特定比较关系的位置。这个性质在“柱状图中最大的矩形”这类题目里是核心。第三个细节边界条件。数组为空直接返回空数组数组只有一个元素时结果应该是 [-1] 或 [null]所有元素都相等时不会有任何弹栈发生结果全部是 -1。这些边界不用额外特判因为初始化和循环逻辑天然覆盖了但测试的时候要想到。4. 经典场景与题目映射——通解怎么用4.1 下一个更大元素系列这类题有两种常见形态一种是无重复数组一种是循环数组。无重复数组的版本可以直接套模板。循环数组的处理方式有一个经典技巧把数组复制一倍拼接起来遍历长度为原来的两倍下标对原长度取模这样就能模拟环形结构。另一种更省内存的方式是遍历两遍用i % n来访问元素效果完全一样。我在实战中更推荐遍历两遍的方式因为拼接数组在 n 很大的时候浪费空间而两遍遍历只增加了常数时间的开销代码也很干净。4.2 柱状图中最大的矩形这道题是单调栈的经典应用题。给定一个柱状图的高度数组找到能勾勒出的最大矩形面积。暴力解法是枚举每个柱子作为矩形的高然后向左右扩展边界复杂度 O(n²)。单调栈解法就变成了找到每个柱子左边第一个比它矮的位置、右边第一个比它矮的位置这两个位置之间就是当前柱子能作为高度的最大宽度。这正好是“左右两侧最近的更小值”的典型应用。套用左侧更小和右侧更小的模板得到左右边界然后面积 高度 × (right[i] - left[i] - 1)取全局最大值。我当初在这道题上踩过一个坑左右边界初始化。如果某个柱子左边没有更矮的它的 left 边界应该是 -1右边没有更矮的它的 right 边界应该是 n。否则计算宽度时会漏掉边界柱子导致结果变小。细节上必须有这个“哨兵”意识。4.3 接雨水问题接雨水也是单调栈的高频出题点本质上是在找一个元素左右两侧最近的高度关系。用单调栈处理时核心思路是当出现“中间低、两边高”的结构时中间低处就能接到雨水。栈内维护的是递减的高度下标当新元素比栈顶高的时候把栈顶弹出此时弹出的位置就是一个凹陷它的积水深度取决于它左侧的新栈顶和右侧的新元素中较矮的那个。这个题目比单纯的“找更大/更小”多了一步——需要计算面积但底层的查找逻辑依然是最近的更大值/更小值关系。很多读者会觉得这题难其实难的是把“积水区间”和“左右边界”的关系看透。一旦你能熟练写出上一节的四个模板函数这题的骨架已经在了。4.4 每日温度问题这个题是单调栈最入门、最友好的应用给定每日气温列表返回一个列表每个位置表示要等多少天才会出现更高温度。翻译一下就是对每个元素找右边第一个比它大的元素下标然后算下标的差值。这个和nextGreaterElement的唯一区别是返回的不是下标本身而是“下标差值”。这个题我建议作为单调栈的入门第一题。因为它没有面积计算、没有宽度合并、没有循环数组纯粹就是查最近更大值位置然后把模板吃透。很多教学材料把它和柱状图混在一起讲导致初学者同时面对两个陌生概念非常劝退。5. 常见问题与排查技巧实录5.1 弹栈条件写反导致结果全错这是我见过最多的问题也是自己刚开始学的时候栽过的地方。举个例子找右侧第一个比当前元素大的值如果你错误地写成了while (stack.length 0 nums[i] nums[stack[stack.length - 1]])那么你会把“新元素比栈顶元素小”作为弹栈条件。这样栈里元素会不断累积完全无法触发任何“找到答案”的逻辑最后结果全部是 -1。排查方式也很简单随便拿一个小数组比如 [1, 3, 2]手动走一遍你的 while 循环。第一个元素进栈第二个元素 3 比栈顶 1 大应该弹栈但你写的是小于号没弹出第三个元素 2 比栈顶 3 小也没弹出。整个栈越堆越满没有任何答案产生。走到这一步99% 是比较符号写反了。5.2 栈里存值不存下标很多初学者图省事直接把值放进栈里结果算出来的答案是对的但一旦题目要求返回下标或计算距离又要回头改代码。我的习惯是只要使用单调栈一律存下标。即使题目只要求返回最大值我也用下标去访问因为这样代码的可扩展性最好。面试中你很难预判追问方向存下标等于给自己留了后路。5.3 相等元素的处理题目没有说明数组是否包含相等元素时这里就藏着坑。找“第一个比自己大”时相等元素不能触发弹栈找“第一个比自己小”时相等元素也不能触发弹栈。所以用和不要用和这是默认选择。但如果题目要求是“第一个不小于”或“第一个不大于”那就要改成或。这种细微差别在具体题目里经常成为区分点。5.4 单调栈的时间复杂度为什么是 O(n)这是一个面试常问的问题要能讲清楚。每个元素最多入栈一次、出栈一次while 循环中所有迭代的总次数不超过 2n所以整体是线性复杂度。不要被“循环里还有循环”的表象迷惑内层 while 是均摊 O(1) 的因为每个元素只会被弹出一次。我用一个生活比喻来解释给朋友听就像是给每个进教室的人安排座位每个人坐下后起身离开教室最多一次。虽然看起来一直在忙活但总的“坐下—离开”次数不会超过人数的两倍。5.5 如何肉眼验证结果我要求自己写完模板后一定用一个小例子在纸上跑一遍。拿 [2, 1, 4, 3] 测右侧更大值i0栈空push 0i1nums[1]1不比栈顶 2 大push 1i2nums[2]4比栈顶下标 1 的元素 1 大弹出 1res[1]4继续比栈顶下标 0 的元素 2 大弹出 0res[0]4栈空push 2i3nums[3]3比栈顶下标 2 的元素 4 小push 3最后栈里剩下标 2 和 3res[2]-1res[3]-1结果应该是 [4, 4, -1, -1]。检查一下数组 [2, 1, 4, 3] 里2 的右边第一个更大是 41 的右边第一个更大是 44 的右边没有更大3 的右边没有更大。完全正确。这种手跑的方式在初学阶段非常有效也是我向所有读者建议的调试手段。5.6 从二维扩展中得到的经验单调栈的模板掌握之后很多看似高级的问题会迎刃而解。比如“矩阵中最大矩形”、“统计子矩阵数量”等题目往往需要先对每一行或每一列进行预处理把问题转化为一维的柱状图问题然后再套单调栈。这类二维问题的关键一步在于如何构造出每个位置的高度数组。我的建议是先在一维层面把四个模板写到肌肉记忆的程度再去看二维扩展否则容易混淆。实际项目中我还会把四个模板封装成一个小工具模块传入一个数组和配置项直接返回四个结果。这种做法在竞赛和面试准备阶段帮助极大因为它把大量重复代码收敛成了一个函数调试起来异常方便。6. 进阶优化与模式识别——如何把模板用到炉火纯青6.1 统一封装成一个多功能函数如果你和我一样前前后后写过不下二十道单调栈题目会发现每次都在复制同样的结构。与其反复改符号不如直接封装成一个函数。用 JavaScript 写的话可以是这样的思路function monotonicStack(nums, mode) { const n nums.length; const res new Array(n).fill(-1); const stack []; const range mode.includes(left) ? Array.from({ length: n }, (_, i) n - 1 - i) : Array.from({ length: n }, (_, i) i); const shouldPop mode.includes(greater) ? (cur, top) cur top : (cur, top) cur top; for (const i of range) { while (stack.length 0 shouldPop(nums[i], nums[stack[stack.length - 1]])) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }这个封装不算最优主要是给读者展示一种“参数化比较条件 参数化遍历方向”的设计思路。真正用的时候如果你不想写这么抽象那就手写四个函数20 行不到反而更直观。6.2 用单调栈解决区间问题的高阶思路单调栈不仅能定位最近更大/更小值还能定位“以某个元素为最小值的最大区间”这是它更高级的用法。想象一个数组你想知道每个元素作为最小值时能覆盖的最远区间是什么。你只需要找这个元素左边第一个比它小的位置和右边第一个比它小的位置两个位置之间就是它能作为最小值的最远范围。这个区间信息在很多统计类问题里非常有用。比如有一类题目让你计算“所有子数组的最小值之和”如果你枚举所有子数组复杂度是 O(n²)。但利用单调栈找出每个元素作为最小值的区间范围后每个元素作为最小值的子数组数量可以直接算出来再用乘法分配律累积结果整体复杂度降到 O(n)。这类题目强烈推荐在掌握基础模板后专门练一练它是单调栈从“会写”到“会用”的质变点。6.3 与双指针、前缀和的组合单调栈经常不是单独出现的它会和前缀和、差分数组组合在一起。比如在某些需要计算“给定数组中所有区间最小值之和”的场景中先用单调栈找到每个元素的左右边界再用前缀和快速计算区间贡献整个过程行云流水。组合应用的窍门是先问自己每个元素对最终答案的贡献是什么如果贡献和“它能成为最大/最小的范围”有关单调栈几乎总是第一选择。6.4 我常做的三类练习设计如果你在准备面试或者竞赛我建议把单调栈的练习分成三个阶段第一阶段只写四个模板函数。不追求速度但要保证每次都能不假思索地写对弹栈条件、遍历方向、记录方式。这个阶段的目标是把代码结构刻进肌肉记忆。第二阶段做三道经典题。每日温度、柱状图中最大的矩形、接雨水。这三题分别对应“找更大值”“双侧找更小值并计算宽度”“双侧找更大值并计算面积”覆盖了单调栈的主要考点。第三阶段做一道二维变体题。比如把矩阵按行累加后转换成一维柱状图问题。这一步能显著提升你对底层模式的识别能力。我在带过的几个初学小伙伴身上验证过按照这个节奏练基本一周内就能从零到能够独立解决中等难度的单调栈题目。这个阶段的练习价值非常大远超过单纯刷题的数量意义。7. 个人经验与避坑心得——写给正在刷题的你最后分享一些我在反复使用单调栈过程中的真实体验。我最开始接触这个知识点时也觉得它不过是一个“找最近更大值”的小技巧。但后来在一次处理实际数据的需求中遇到一个百万级日志序列需要为每一条日志找到它前面最近的一条异常记录朴素做法跑了几分钟也没出结果。当时我忽然想到单调栈改完之后耗时降到了毫秒级。从那时起我对这个小技巧有了完全不同的认识——它不是一个应试工具而是一个真正能在数据量面前改变效率的算法思想。如果你正在学习这块内容我的建议是不要硬背代码。先理解那个“弹栈瞬间即答案”的核心逻辑然后用一组固定的小数据反复手推直到你看到任何“最近更大/更小”的问题第一反应不是写双重循环而是想“这里能不能用单调栈”。还要提醒一点写模板的时候不要图省事把判断条件直接内联到循环里先用变量名把“ isGreater ”这样的语义表达出来代码会清晰很多调试的时候也更容易发现问题。这个习惯在写到第 10 个题目时会给你带来极大的优势。单调栈是一门“会者不难”的技术。把这个通解吃透你以后再遇到各种花式包装的题目比如循环数组、二维矩阵、区间贡献统计会发现它们不过是在这个核心模板上增加了一些外围逻辑。掌握了核心一切都会显得理所当然。 
长河君 · 2026/10/21 9:02:38 · 阅读 1.2k 单调栈通解：线性时间解决最近更大/更小值问题
1. 单调栈的本质——先搞清楚它在解决什么问题1.1 暴力解法为什么让人头疼先想一个最直观的问题给你一个数组 [2, 1, 4, 3]让你找出每个元素右边第一个比它大的数你会怎么做绝大多数人第一反应是双重循环外层遍历每个元素内层从当前位置往后找遇到第一个更大的就停下。这个思路没有任何问题但内层循环的代价是 O(n)整体复杂度是 O(n²)。数据量小的时候问题不大一旦 n 到了 10⁵ 甚至 10⁶ 的量级双重循环跑起来就是灾难。我在实际刷题中体感最深的是很多题目表面上看是“找某个位置的最近更大值/最近更小值”但只要你开始写双循环基本就掉进了超时的陷阱。这道题真正考察的不是你会不会写循环而是你能不能把“每个元素与它相邻的更大/更小值之间的关系”用一种线性时间的方式统一处理。1.2 单调栈的核心思想单调栈这个名字听着有点唬人说白了就是一种栈栈内元素按照从栈底到栈顶的顺序保持单调递增或单调递减。它解决的问题非常集中给定一个序列快速找到每个元素左边或右边第一个比它大或比它小的元素位置。注意关键词是“第一个”不是“最大”也不是“最小”而是某种比较关系下距离最近的那个边界元素。为了帮助理解我经常用一个生活化的类比想象一个班级里按身高排队每个人想知道离自己最近的前面那个人里第一个比自己高的人是谁。每个人进入队伍的时候如果发现队尾的人比自己矮那队尾的人马上就知道答案了——答案是当前这个比自己高的人然后队尾的人就可以离开队伍。反复执行这个“矮的出队、高的留下”的操作队伍里的人始终是从低到高排的。这就是单调栈的运作模式新元素进来的时候把栈顶那些“不如自己”的元素赶出去因为这些元素在比较关系中已经确定了它们要找的边界。每个元素最多入栈一次、出栈一次所以总时间复杂度是 O(n)。1.3 单调递增栈和单调递减栈怎么选这里有个高频混淆点。很多初学者分不清什么时候用单调递增栈、什么时候用单调递减栈我给出一个非常实用的判断方法要找左边或右边第一个比自己大的元素维护的是从栈底到栈顶单调递减的栈。因为当新元素比栈顶元素大时栈顶立刻找到了“第一个比自己大”的答案。要找左边或右边第一个比自己小的元素维护的是从栈底到栈顶单调递增的栈。因为当新元素比栈顶元素小时栈顶立刻找到了“第一个比自己小”的答案。这个很容易记反。我的记忆方式很简单你要找“大的”那就让“大的”能产生威胁也就是新元素大的时候会触发弹栈你要找“小的”那就让“小的”产生威胁也就是新元素小的时候会触发弹栈。触发弹栈的瞬间就是被弹栈元素得到答案的瞬间。2. 通解的推导——四种情况如何统一成一版代码2.1 问题的完整形式标题里说的“通解”我理解成这样一个完整的问题族给定一个数组 nums要求每个元素左边第一个比它小的元素下标或值每个元素左边第一个比它大的元素每个元素右边第一个比它小的元素每个元素右边第一个比它大的元素这四种情况看起来是四个不同的问题代码也可能四份但从单调栈的角度来看通解只需要一套模板。核心区别只有三点遍历方向从左往右还是从右往左、比较条件什么时候弹栈、记录位置记录左边还是右边。2.2 什么时候更新答案这是整个通解里最关键的判断逻辑。每次新元素 nums[i] 尝试入栈时如果栈顶元素已经“找到了答案”就把栈顶弹出并在弹出的瞬间给栈顶元素的位置设置结果。举个例子我们要找右边第一个比自己大的元素。从左往右遍历当新元素 nums[i] 大于栈顶元素时对于栈顶元素来说nums[i] 就是它右边第一个比它大的值因为我们是顺着数组顺序扫描的第一个遇到的更大的值天然就是“右边第一个”。同理要找右边第一个比自己小的元素从左往右遍历当新元素 nums[i] 小于栈顶元素时栈顶元素就得到了它的答案。那找左边第一个比自己大或者比自己小呢两种思路都行思路一从右往左遍历这样“左边”相对于遍历方向反而变成了“右边”镜像处理。思路二还是从左往右遍历但把答案记录逻辑反过来也就是在扫描过程中维护一个已经见过的元素的单调栈对于每一个新元素栈里存的都是它左边所有还没有找到答案的元素弹出的时机依然受比较条件控制。我实际用下来更推荐“统一从左往右扫描 反向记录”的方案因为这样左右两种情况代码结构完全一致只需要把比较符号换一下、记录方式换一下。2.3 统一模板思路先定义几个变量res结果数组初始化为 -1 或 null表示没找到stack存的是元素下标不是元素值这一点非常重要从左往右遍历 nums对于每个 iwhile 栈不为空 且 当前元素与栈顶元素满足弹栈条件: 栈顶下标 top stack.pop() res[top] i // 记录右侧最近值的位置 stack.push(i)这里“弹栈条件”就是问题的核心开关右侧最近更大值nums[i] nums[stack[-1]]右侧最近更小值nums[i] nums[stack[-1]]如果你要的是左侧最近值有两种处理方式方式一上面的模板得到的是“右侧最近值”然后对这个模板遍历方向反转从右往左得到的就是“左侧最近值”。方式二从左往右遍历当弹出栈顶时栈顶的下一个栈内元素就是栈顶元素左侧最近的候选值。我建议先把右侧的两种情况吃透左侧的用反转遍历方向来镜像解决。这样需要记忆的内容最少不容易出错。3. 从模板到代码——四种变体的具体实现3.1 右侧最近更大值的完整实现先看最经典的“右侧第一个比自己大的元素”。function nextGreaterElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i 0; i n; i) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }这里我特意在res[top]里存的是值有些题目要求存下标那就是res[top] i。建议先统一存下标因为有了下标可以随时取值反过来不行。这个细节看起来不起眼但在追问环节很容易救你一命。有些人会问为什么初始化是 -1因为如果一个元素后面没有更大的数它的结果应该是个特殊标识。用 -1 在竞赛和面试里都是默认做法不用纠结。3.2 右侧最近更小值的实现把比较符号改成小于号就完成了。function nextSmallerElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i 0; i n; i) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }区别只有变成了。这就是通解的力量——你不必把四种情况当作四个独立题目去背只要理解“弹栈瞬间即答案”剩下的都是条件切换。3.3 左侧最近更大值与左侧最近更小值左侧版本我推荐直接反转遍历方向从右往左复用右侧的模板逻辑。function previousGreaterElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i n - 1; i 0; i--) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }注意看代码结构和nextGreaterElement几乎一致只是循环从i 0; i n变成了i n - 1; i 0比较符号不变。因为在“从右往左看”的世界里右侧变成了我们的主扫描方向而被弹出的元素得到的答案就是它在这个反向扫描中遇到的第一个更大值从原数组角度看就是它左侧的最近更大值。同理可得function previousSmallerElement(nums) { const n nums.length; const res new Array(n).fill(-1); const stack []; for (let i n - 1; i 0; i--) { while (stack.length 0 nums[i] nums[stack[stack.length - 1]]) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }四个函数放在一起看就是两处变量一个循环方向一个比较符号。能用一个模板理解的东西就不要拆成四个知识点来记。3.4 写代码时的三个关键细节第一个细节栈里存的是下标而不是值。为什么因为很多后续题目需要知道位置差、计算宽度、计算面积只有下标才能推导出来。如果只存值位置信息就丢了。第二个细节弹栈之后栈里剩下的元素之间的关系。栈始终保持单调性也就是说当你弹掉若干元素之后新的栈顶一定是当前元素之前最近且满足特定比较关系的位置。这个性质在“柱状图中最大的矩形”这类题目里是核心。第三个细节边界条件。数组为空直接返回空数组数组只有一个元素时结果应该是 [-1] 或 [null]所有元素都相等时不会有任何弹栈发生结果全部是 -1。这些边界不用额外特判因为初始化和循环逻辑天然覆盖了但测试的时候要想到。4. 经典场景与题目映射——通解怎么用4.1 下一个更大元素系列这类题有两种常见形态一种是无重复数组一种是循环数组。无重复数组的版本可以直接套模板。循环数组的处理方式有一个经典技巧把数组复制一倍拼接起来遍历长度为原来的两倍下标对原长度取模这样就能模拟环形结构。另一种更省内存的方式是遍历两遍用i % n来访问元素效果完全一样。我在实战中更推荐遍历两遍的方式因为拼接数组在 n 很大的时候浪费空间而两遍遍历只增加了常数时间的开销代码也很干净。4.2 柱状图中最大的矩形这道题是单调栈的经典应用题。给定一个柱状图的高度数组找到能勾勒出的最大矩形面积。暴力解法是枚举每个柱子作为矩形的高然后向左右扩展边界复杂度 O(n²)。单调栈解法就变成了找到每个柱子左边第一个比它矮的位置、右边第一个比它矮的位置这两个位置之间就是当前柱子能作为高度的最大宽度。这正好是“左右两侧最近的更小值”的典型应用。套用左侧更小和右侧更小的模板得到左右边界然后面积 高度 × (right[i] - left[i] - 1)取全局最大值。我当初在这道题上踩过一个坑左右边界初始化。如果某个柱子左边没有更矮的它的 left 边界应该是 -1右边没有更矮的它的 right 边界应该是 n。否则计算宽度时会漏掉边界柱子导致结果变小。细节上必须有这个“哨兵”意识。4.3 接雨水问题接雨水也是单调栈的高频出题点本质上是在找一个元素左右两侧最近的高度关系。用单调栈处理时核心思路是当出现“中间低、两边高”的结构时中间低处就能接到雨水。栈内维护的是递减的高度下标当新元素比栈顶高的时候把栈顶弹出此时弹出的位置就是一个凹陷它的积水深度取决于它左侧的新栈顶和右侧的新元素中较矮的那个。这个题目比单纯的“找更大/更小”多了一步——需要计算面积但底层的查找逻辑依然是最近的更大值/更小值关系。很多读者会觉得这题难其实难的是把“积水区间”和“左右边界”的关系看透。一旦你能熟练写出上一节的四个模板函数这题的骨架已经在了。4.4 每日温度问题这个题是单调栈最入门、最友好的应用给定每日气温列表返回一个列表每个位置表示要等多少天才会出现更高温度。翻译一下就是对每个元素找右边第一个比它大的元素下标然后算下标的差值。这个和nextGreaterElement的唯一区别是返回的不是下标本身而是“下标差值”。这个题我建议作为单调栈的入门第一题。因为它没有面积计算、没有宽度合并、没有循环数组纯粹就是查最近更大值位置然后把模板吃透。很多教学材料把它和柱状图混在一起讲导致初学者同时面对两个陌生概念非常劝退。5. 常见问题与排查技巧实录5.1 弹栈条件写反导致结果全错这是我见过最多的问题也是自己刚开始学的时候栽过的地方。举个例子找右侧第一个比当前元素大的值如果你错误地写成了while (stack.length 0 nums[i] nums[stack[stack.length - 1]])那么你会把“新元素比栈顶元素小”作为弹栈条件。这样栈里元素会不断累积完全无法触发任何“找到答案”的逻辑最后结果全部是 -1。排查方式也很简单随便拿一个小数组比如 [1, 3, 2]手动走一遍你的 while 循环。第一个元素进栈第二个元素 3 比栈顶 1 大应该弹栈但你写的是小于号没弹出第三个元素 2 比栈顶 3 小也没弹出。整个栈越堆越满没有任何答案产生。走到这一步99% 是比较符号写反了。5.2 栈里存值不存下标很多初学者图省事直接把值放进栈里结果算出来的答案是对的但一旦题目要求返回下标或计算距离又要回头改代码。我的习惯是只要使用单调栈一律存下标。即使题目只要求返回最大值我也用下标去访问因为这样代码的可扩展性最好。面试中你很难预判追问方向存下标等于给自己留了后路。5.3 相等元素的处理题目没有说明数组是否包含相等元素时这里就藏着坑。找“第一个比自己大”时相等元素不能触发弹栈找“第一个比自己小”时相等元素也不能触发弹栈。所以用和不要用和这是默认选择。但如果题目要求是“第一个不小于”或“第一个不大于”那就要改成或。这种细微差别在具体题目里经常成为区分点。5.4 单调栈的时间复杂度为什么是 O(n)这是一个面试常问的问题要能讲清楚。每个元素最多入栈一次、出栈一次while 循环中所有迭代的总次数不超过 2n所以整体是线性复杂度。不要被“循环里还有循环”的表象迷惑内层 while 是均摊 O(1) 的因为每个元素只会被弹出一次。我用一个生活比喻来解释给朋友听就像是给每个进教室的人安排座位每个人坐下后起身离开教室最多一次。虽然看起来一直在忙活但总的“坐下—离开”次数不会超过人数的两倍。5.5 如何肉眼验证结果我要求自己写完模板后一定用一个小例子在纸上跑一遍。拿 [2, 1, 4, 3] 测右侧更大值i0栈空push 0i1nums[1]1不比栈顶 2 大push 1i2nums[2]4比栈顶下标 1 的元素 1 大弹出 1res[1]4继续比栈顶下标 0 的元素 2 大弹出 0res[0]4栈空push 2i3nums[3]3比栈顶下标 2 的元素 4 小push 3最后栈里剩下标 2 和 3res[2]-1res[3]-1结果应该是 [4, 4, -1, -1]。检查一下数组 [2, 1, 4, 3] 里2 的右边第一个更大是 41 的右边第一个更大是 44 的右边没有更大3 的右边没有更大。完全正确。这种手跑的方式在初学阶段非常有效也是我向所有读者建议的调试手段。5.6 从二维扩展中得到的经验单调栈的模板掌握之后很多看似高级的问题会迎刃而解。比如“矩阵中最大矩形”、“统计子矩阵数量”等题目往往需要先对每一行或每一列进行预处理把问题转化为一维的柱状图问题然后再套单调栈。这类二维问题的关键一步在于如何构造出每个位置的高度数组。我的建议是先在一维层面把四个模板写到肌肉记忆的程度再去看二维扩展否则容易混淆。实际项目中我还会把四个模板封装成一个小工具模块传入一个数组和配置项直接返回四个结果。这种做法在竞赛和面试准备阶段帮助极大因为它把大量重复代码收敛成了一个函数调试起来异常方便。6. 进阶优化与模式识别——如何把模板用到炉火纯青6.1 统一封装成一个多功能函数如果你和我一样前前后后写过不下二十道单调栈题目会发现每次都在复制同样的结构。与其反复改符号不如直接封装成一个函数。用 JavaScript 写的话可以是这样的思路function monotonicStack(nums, mode) { const n nums.length; const res new Array(n).fill(-1); const stack []; const range mode.includes(left) ? Array.from({ length: n }, (_, i) n - 1 - i) : Array.from({ length: n }, (_, i) i); const shouldPop mode.includes(greater) ? (cur, top) cur top : (cur, top) cur top; for (const i of range) { while (stack.length 0 shouldPop(nums[i], nums[stack[stack.length - 1]])) { const top stack.pop(); res[top] nums[i]; } stack.push(i); } return res; }这个封装不算最优主要是给读者展示一种“参数化比较条件 参数化遍历方向”的设计思路。真正用的时候如果你不想写这么抽象那就手写四个函数20 行不到反而更直观。6.2 用单调栈解决区间问题的高阶思路单调栈不仅能定位最近更大/更小值还能定位“以某个元素为最小值的最大区间”这是它更高级的用法。想象一个数组你想知道每个元素作为最小值时能覆盖的最远区间是什么。你只需要找这个元素左边第一个比它小的位置和右边第一个比它小的位置两个位置之间就是它能作为最小值的最远范围。这个区间信息在很多统计类问题里非常有用。比如有一类题目让你计算“所有子数组的最小值之和”如果你枚举所有子数组复杂度是 O(n²)。但利用单调栈找出每个元素作为最小值的区间范围后每个元素作为最小值的子数组数量可以直接算出来再用乘法分配律累积结果整体复杂度降到 O(n)。这类题目强烈推荐在掌握基础模板后专门练一练它是单调栈从“会写”到“会用”的质变点。6.3 与双指针、前缀和的组合单调栈经常不是单独出现的它会和前缀和、差分数组组合在一起。比如在某些需要计算“给定数组中所有区间最小值之和”的场景中先用单调栈找到每个元素的左右边界再用前缀和快速计算区间贡献整个过程行云流水。组合应用的窍门是先问自己每个元素对最终答案的贡献是什么如果贡献和“它能成为最大/最小的范围”有关单调栈几乎总是第一选择。6.4 我常做的三类练习设计如果你在准备面试或者竞赛我建议把单调栈的练习分成三个阶段第一阶段只写四个模板函数。不追求速度但要保证每次都能不假思索地写对弹栈条件、遍历方向、记录方式。这个阶段的目标是把代码结构刻进肌肉记忆。第二阶段做三道经典题。每日温度、柱状图中最大的矩形、接雨水。这三题分别对应“找更大值”“双侧找更小值并计算宽度”“双侧找更大值并计算面积”覆盖了单调栈的主要考点。第三阶段做一道二维变体题。比如把矩阵按行累加后转换成一维柱状图问题。这一步能显著提升你对底层模式的识别能力。我在带过的几个初学小伙伴身上验证过按照这个节奏练基本一周内就能从零到能够独立解决中等难度的单调栈题目。这个阶段的练习价值非常大远超过单纯刷题的数量意义。7. 个人经验与避坑心得——写给正在刷题的你最后分享一些我在反复使用单调栈过程中的真实体验。我最开始接触这个知识点时也觉得它不过是一个“找最近更大值”的小技巧。但后来在一次处理实际数据的需求中遇到一个百万级日志序列需要为每一条日志找到它前面最近的一条异常记录朴素做法跑了几分钟也没出结果。当时我忽然想到单调栈改完之后耗时降到了毫秒级。从那时起我对这个小技巧有了完全不同的认识——它不是一个应试工具而是一个真正能在数据量面前改变效率的算法思想。如果你正在学习这块内容我的建议是不要硬背代码。先理解那个“弹栈瞬间即答案”的核心逻辑然后用一组固定的小数据反复手推直到你看到任何“最近更大/更小”的问题第一反应不是写双重循环而是想“这里能不能用单调栈”。还要提醒一点写模板的时候不要图省事把判断条件直接内联到循环里先用变量名把“ isGreater ”这样的语义表达出来代码会清晰很多调试的时候也更容易发现问题。这个习惯在写到第 10 个题目时会给你带来极大的优势。单调栈是一门“会者不难”的技术。把这个通解吃透你以后再遇到各种花式包装的题目比如循环数组、二维矩阵、区间贡献统计会发现它们不过是在这个核心模板上增加了一些外围逻辑。掌握了核心一切都会显得理所当然。