训练营第46天正式进入单调栈专题。代码随想录的进度安排到这里栈和队列基础刚巩固完双指针、滑动窗口也刷过不少突然又冒出来一个“单调栈”。第一反应是栈就栈怎么还单调刷完三道题再回头看才发现Carl哥为什么把这个专题单独拎出来。单调栈专治一类问题在一维数组里找每个元素右侧或左侧第一个比自己大或小的元素。暴力解法三分钟就能写出来可一旦数据量上来O(n²) 必超时。今天这篇就把单调栈专题1的完整思路、标准模板和我踩过的坑一次说清楚。这一篇也算一次“单调栈揭秘”适合刚接触单调栈的新手也适合想系统整理模板的刷题人。1. 单调栈到底解决了什么问题1.1 暴力解法为什么慢从每日温度说起先看LeetCode 739每日温度。题目给一个气温列表 temperatures [73, 74, 75, 71, 69, 72, 76, 73]要返回每一天后第一次升温需要等待的天数如果之后没有更高温度就记0。输出应该是 [1,1,4,2,1,1,0,0]。第0天温度73第1天74就升温所以result[0]1。第2天75之后要隔4天到76才升温所以result[2]4。暴力解法怎么写两层循环外层固定一个i内层从i1开始往右扫找第一个比temperatures[i]大的元素j然后result[i]j-i。找不到就是0。这个解法逻辑很直白但有一个致命问题每个元素都在重复扫描后面那段数组。比如一个升序数组 [1, 2, 3, 4, ..., n]第一个元素1要扫到数组末尾才能找到2第二个元素2要扫到末尾才能找到3越往前的位置扫描次数越长整体退化到O(n²)。为什么慢因为这些“后面的信息”没有被保存下来。暴力解法每次都是从零开始往后查没有任何记忆。单调栈的思路本质上是空间换时间用一个栈把“还没找到答案的下标”暂时存起来等新元素出现时去栈里逐一结算。每个元素最多入栈一次、出栈一次遍历一遍就能完成全部结算所以整体O(n)。这就像排队买奶茶队伍里每个人都在等一个比自己高的人出现。暴力办法是每个人都回头往后张望谁也不知道后面什么时候来个高的。单调栈则是让所有“还没等到结果的人”站到栈里新来的人一出现如果比栈顶的人高就直接告诉栈顶的人“我就是你要等的”栈顶离开队伍如果新来的人比栈顶矮就继续入栈等待。这样每个人最多被看一次效率自然高。1.2 单调栈的本质把“没找到答案的人”挂在栈里单调栈并不是什么全新数据结构它就是一个普通栈加上一条额外约束栈内元素对应的数组值从栈底到栈顶保持单调递增或递减。这个约束是用来干嘛的用来保证“什么时候该结算”是确定性的。我们在线性遍历数组时会遇到两种元素一种马上就能结算当前元素就是某些待定元素的下一个更大值一种暂时结算不了当前元素太小先入栈等着。如果栈内元素是乱序的遇到新元素时你无法判断该不该弹出栈顶甚至可能要反复比较。一旦栈内有序新元素只要和栈顶比较一次就能决定连锁弹出的条件。举个生活化例子。假设栈里存着一串等待答案的人他们身高从底到顶是从高到矮排列的。这时候来了一个新人身高1米78。你和栈顶那个最矮的人比如果比他高就说明栈顶的人等到答案了弹出结算接下来继续跟新的栈顶比如果还比下一个高继续弹出直到遇到一个比自己高的人或者栈空停止弹出然后自己入栈。这个过程像不像“比身高连续碾压”因为栈内有序你可以放心用while循环连续弹出凡是比新元素矮的答案都是“新元素”不需要额外判断。这里要提醒一点约定俗成的说法很多。代码随想录里讲单调栈时强调求“下一个更大元素”用的是“从栈底到栈顶递减”的栈求“下一个更小元素”用的是“从栈底到栈顶递增”的栈。但也有人从栈顶往栈底看叫法完全相反。所以我建议别死记“递增栈”还是“递减栈”直接记住出栈条件更靠谱。1.3 两种形态更大找递减栈更小找递增栈用单调栈解决“右边第一个更大元素”核心出栈条件是 nums[i] nums[stack.peek()]。因为栈内保留的是“还没找到更大值的下标”而这些下标对应的值从栈底到栈顶是递减的栈顶是最小值。新元素只要比这个最小值大栈顶就找到了答案如果比栈顶还小说明它连当前最矮的都比不过自然也不是其他栈内元素的答案直接入栈即可。反过来求“右边第一个更小元素”出栈条件是 nums[i] nums[stack.peek()]。栈内从栈底到栈顶递增栈顶是最大值。新元素只要比当前最大值小栈顶就等到了右侧第一个更小值连续弹出结算如果比栈顶还大说明它也不可能成为其他栈内元素的更小答案入栈等待。所以你只需要问自己一个问题我找的是“更大”还是“更小”找更大就用“大于号出栈”找更小就用“小于号出栈”。这个判断比纠结栈的命名重要得多。等把这个方向搞清楚再看是求左侧还是右侧无非是遍历方向改一下比如从右到左遍历就能求左侧第一个更大或更小原理是对称的。2. 单调栈模板三行while撑起整个专题2.1 模板逐行拆解下标才是主角先说标准模板。以“求nums中每个元素右侧第一个更大元素的下标”为例代码长这样public int[] nextGreaterElementIndex(int[] nums) { int n nums.length; int[] result new int[n]; Arrays.fill(result, -1); DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { while (!stack.isEmpty() nums[i] nums[stack.peek()]) { int idx stack.pop(); result[idx] i; } stack.push(i); } return result; }这段代码很精简但每一行都值得拆开看。第一栈里存的是下标不是值。为什么因为存下标既可以拿到对应元素的值 nums[idx]又可以知道它的位置。特别是每日温度这种要求间隔天数的题你必须知道“原下标i - 栈顶下标idx”才能算出天数。如果只存值位置信息就丢了后面还要用map去映射下标非常麻烦。第二while循环的判断条件是 nums[i] nums[stack.peek()]而不是 i stack.peek()。初学者经常把比较对象搞错拿下标和下标比那完全是错的。我们关注的是数组元素的大小关系下标只是定位工具。第三结算时弹出的idx就是“已经找到答案的下标”答案就是当前i或者nums[i]。至于result[idx]到底填什么要看题目。739要填天数差所以result[idx] i - idx如果题目问值就填nums[i]。第四while结束后当前下标i入栈。为什么不入栈之前直接入栈因为要先把所有比nums[i]小的栈顶元素都结算掉保证栈内从底到顶保持递减再把自己放进去继续维持单调性。这就是单调栈的“自我维护”。这个模板的时间复杂度是O(n)空间复杂度O(n)。每个元素最多入栈一次出栈一次循环内部的while总执行次数不会超过n次所以整体是线性的。空间上最坏情况下栈里可能存n个元素比如降序数组每个元素都进栈等着但即使这样也只会O(n)。2.2 “更大”还是“更小”比较符号定方向我见过太多人把单调栈模板倒背如流结果一换题就错。问题往往出在出栈条件选错。这里给一个实用判断法找“右侧第一个更大元素”从左到右遍历出栈条件写。找“右侧第一个更小元素”从左到右遍历出栈条件写。找“左侧第一个更大元素”从右到左遍历其他条件不变。找“左侧第一个更小元素”从右到左遍历其他条件不变。也就是说“更大”和“更小”决定比较符号左右方向决定遍历顺序。我用这个思路去套所有单调栈题目基本不会跑偏。为什么这么说你想想看栈里存的都是“还没找到答案的人”。“更大”意味着新元素要高过别人才能当答案所以是“更小”意味着新元素要矮过别人才能当答案所以是。符号本身就是需求。还有些题目虽然用了单调栈但不是直接求“下一个更大/更小”而是换了个更隐蔽的包装。比如接雨水那个题本质上要找到每个位置左右两边第一个更高的柱子这其实是左右两个单调栈问题合并。等你把739、496、503这些基础题跑通再去做接雨水会发现它就是多个单调栈套路的组合。2.3 记忆口诀与三步自检我整理了一个顺手的自检流程写代码前问自己三个问题我要找的是右侧还是左侧这决定for循环从哪边遍历。我要找的是更大还是更小这决定while里用还是。答案要下标还是值这决定result里填什么以及栈里存什么。这三个问题想清楚再动手写模板基本一次过。我自己的记忆习惯是“大号出栈小号出栈”听起来很怪但好用。找更大就想象成“谁大谁出”找更小就“谁小谁出”。另外画图真的很有用。代码随想录里一直强调栈类问题要画图理解。你不需要画得很精致拿个纸笔数组画成一排柱子栈画在旁边遍历到每个元素都停下来更新一下栈变化三题画下来单调栈的运转过程比看十遍文字解释都清楚。我训练营打卡时遇到看不懂的题第一件事就是画图画完之后代码基本自己能写出来。3. 实战代码三道经典题从暴力到单调栈3.1 LeetCode 739 每日温度第一次用单调栈跑通这道题我建议作为单调栈入门第一题因为它的输出正好是下标差天然逼你必须存下标。还是数组 [73, 74, 75, 71, 69, 72, 76, 73]我们完整走一遍i0栈空把0入栈栈为[0]。 i1温度74大于栈顶0对应的73弹出0result[0]1-01然后1入栈栈为[1]。 i275大于栈顶1对应的74弹出1result[1]12入栈栈为[2]。 i371小于栈顶2对应的753入栈栈为[2,3]。 i469小于栈顶3对应的714入栈栈为[2,3,4]。 i572大于栈顶4对应的69弹出4result[4]5-41继续72大于栈顶3对应的71弹出3result[3]5-32接着72小于栈顶2对应的75停止5入栈栈为[2,5]。 i676大于栈顶5对应的72弹出5result[5]176大于栈顶2对应的75弹出2result[2]6-24栈空6入栈栈为[6]。 i773小于栈顶6对应的767入栈栈为[6,7]。结束。栈内剩下6和7对应76和73右侧没有更高温度保持初始值0。最终result[1,1,4,2,1,1,0,0]和答案一致。这个模拟过程建议自己也手动推一遍。你会发现一个细节在i5时连续弹出两个下标4和3因为它们都是被72“碾压”的而72也同时是它们右侧第一个更大值。这就是while循环的意义——一次新元素到来可以同时结算多个栈内元素效率很高。如果写成暴力解法i3恐怕要扫到i6才能找到答案i4也一样重复劳动很多。代码实现public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] result new int[n]; DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) { int idx stack.pop(); result[idx] i - idx; } stack.push(i); } return result; }注意result数组默认值是0刚好和题目要求“没有更高温度记为0”吻合所以不用额外初始化成-1。3.2 LeetCode 496 下一个更大元素 I单调栈哈希表组合拳739是单个数组内求答案这道题多了一个数组。nums1是nums2的子集要求对nums1中的每个元素在nums2里找它右边的第一个更大元素不存在就返回-1。直接对nums1和nums2双重遍历暴力也能做但单调栈的核心优势会被浪费。更好的思路是先用单调栈把nums2每个元素的下一个更大值都算出来放到哈希表里然后遍历nums1查表。这一步本质上叫“预处理”很多两个数组之间的匹配问题都可以这样处理。把nums2的结果提前算好之后nums1怎么查都只要O(1)时间。public int[] nextGreaterElement(int[] nums1, int[] nums2) { MapInteger, Integer map new HashMap(); DequeInteger stack new ArrayDeque(); for (int num : nums2) { while (!stack.isEmpty() num stack.peek()) { map.put(stack.pop(), num); } stack.push(num); } int[] result new int[nums1.length]; for (int i 0; i nums1.length; i) { result[i] map.getOrDefault(nums1[i], -1); } return result; }注意这道题的栈里存的是值不是下标。为什么因为题目只要求返回“下一个更大的值”不要求索引差而且数组元素是唯一的用值作为map的key刚好合适。这印证了模板部分说的存值还是存下标由题目需求决定。这道题还有个细节循环结束后栈里剩下的元素说明nums2里右侧没有更大值这些值不会被放入map所以查询时会走到getOrDefault的-1不用再做额外处理。3.3 LeetCode 503 下一个更大元素 II循环数组的取模套路这道题把数组变成了循环数组最后一个元素的下一个元素是第一个元素比如[2,1,2]要返回[1,-1,1]。很多人第一反应是把数组复制一份拼在后面变成两倍长度去处理。这个思路没有任何问题但一个更省空间的写法是直接遍历2n次用 i % n 访问元素栈里存真实下标。public int[] nextGreaterElements(int[] nums) { int n nums.length; int[] result new int[n]; Arrays.fill(result, -1); DequeInteger stack new ArrayDeque(); for (int i 0; i 2 * n; i) { int idx i % n; while (!stack.isEmpty() nums[idx] nums[stack.peek()]) { int top stack.pop(); result[top] nums[idx]; } stack.push(idx); } return result; }为什么遍历两遍就够了因为对于循环数组“下一个更大元素”最多跨越数组长度的一半再绕回来两遍遍历已经覆盖了整个环。一个元素如果在第一遍循环里没能找到答案第二遍循环会有机会看到它原本左侧的元素如果两遍都找不到说明它是整个数组中最大的那类元素最终保留-1。这里有个小坑result数组要初始化成-1因为默认情况就是“没有找到更大的”。如果不初始化int数组默认是0会把原本应该返回-1的元素写成0直接错。另外由于栈里存的是原始下标idx可能某个下标会再次被push进去。实测下来这种重复操作不会破坏结果因为它触发的结算结果要么与第一次相同要么就是同一个“更大值”不会把正确结果覆盖成更差的值。这也是社区普遍使用这个写法的原因。4. 常见问题与调试技巧实录4.1 栈里存值还是存下标差之毫厘谬以千里我在训练营打卡时好几个同学都栽在这个问题上。比如739每日温度如果栈里存值弹出之后你只知道“有一个温度被解决了”但不知道它的原始位置就填不了result[i - idx]这个天数差。最后要么加一个map把值映射回下标要么额外开个数组同步维护位置绕一大圈。所以我的建议是除非题目像496那样明确只关心元素值本身否则统一存下标。存下标能同时拿到位置和值信息量最大最万能。真要是遇到存值更简单的题代码也够短到时候再切换思路也不迟。4.2 相等元素怎么处理严格大于还是大于等于这是一个非常典型的边界坑。单调栈处理的是严格意义上的“更大”和“更小”所以出栈条件用的是或不是或。举一个例子nums[2,2]。题目要求右边第一个更大的元素正确结果是[-1,-1]。如果你把while条件写成nums[i] nums[stack.peek()]遍历到第二个2时因为相等就弹出栈里的第一个2并结算result[0]会被填成第二个元素的下标1这就错了。相等不是更大不能结算。反过来如果题目要求的是“右边第一个大于等于”你才需要把条件改成。所以写代码前一定先确认题意。这也是我自检清单里“我要找的是更大还是更小”的深层含义不是简单问方向还要确认是否包含等于。4.3 空栈与越界写循环前的保命小习惯单调栈代码很短但越短越容易在边界上翻车。最常见的两个错误一是while循环里忘了判空。Java的ArrayDeque在peek空栈时会返回null但pop空栈会直接抛异常。如果代码写的是while (nums[i] nums[stack.peek()])当栈为空时就会空指针或异常。正确做法是永远先判!stack.isEmpty()。二是数组索引越界。遍历循环数组时如果你真的去复制一遍数组拼出长度为2n的新数组要小心最后一段索引。用取模写法 i % n 可以完全避免这种越界如果题目固定要返回n长度的结果就强制只处理result[top]这种下标因为top一定是0到n-1之间的原下标不会越界。这类边界问题靠背代码是防不住的。我自己习惯写完代码后手动跑两个极端用例空数组、单元素数组。空数组要保证不抛异常单元素数组要保证结果符合直觉比如496里nums1和nums2只有一个元素答案应该是-1。4.4 调试技巧与速查表调试单调栈最实用的方法是打印每一步的栈状态。很多视觉化debug工具不一定有但你可以朴素地写一行日志System.out.println(i i , stack stack , values stack.stream().map(j - nums[j]).collect(Collectors.toList()));这能直接看到每一步入栈、出栈时栈内下标和值的变化。如果result数组某些位置答案不对对照打印日志基本一眼就能定位是出栈条件错了还是结算填错了。最后给一个单调栈速查表是我现在刷题时常用的题目类型遍历方向出栈条件栈底到栈顶方向默认答案右侧第一个更大左到右nums[i] nums[栈顶]递减-1或0右侧第一个更小左到右nums[i] nums[栈顶]递增-1左侧第一个更大右到左nums[i] nums[栈顶]递减-1左侧第一个更小右到左nums[i] nums[栈顶]递增-1记住这张表单调栈的基础题基本就稳了。后面接雨水、柱状图中最大的矩形本质上是这个表里多个方向组合出来的进阶题等专题2再展开。练到这里我对单调栈最大的体会就是它其实没有绕弯子的新数据结构只是因为我们在遍历时保存了“还没找到答案的下标”又用有序性保证了后续结算顺序。代码随想录把这个专题放到第46天我觉得很合理前面栈、队列、哈希表的底子打好了单调栈就是把这些基础能力集中在一维数组题型上。个人建议写代码前先画一次图画通三道题这套模板你基本再也不忘。我实际跑下来739跑通了496和503就很快因为核心的while逻辑是同一个。后面接雨水和柱状图里的最大矩形本质上就是单调栈专题的延伸等下一篇再聊。