LeetCode 单调栈专题精讲原理、通用模板与实战题解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于本仓库算法专题笔记 thinkings/monotone-stack.en.md 展开系统讲解单调栈Monotonic Stack这一高频面试数据结构的原理、判定规则与通用代码模板并结合仓库内 42. 接雨水、84. 柱状图中最大的矩形、739. 每日温度 等题解源码说明如何将模板落地到真实题目。读完本文你将掌握单调栈的适用场景判别下一个大于 xxx / 下一个小于 xxx、单调递增栈与单调递减栈的判定方法、哨兵法边界处理以及一套可直接套用的 Python3 / JavaScript 通用模板。栈单调栈的基础栈的定义与特征顾名思义单调栈首先是一种栈因此要学单调栈首先要彻底搞懂栈。栈是一种受限的数据结构体现在只允许新的内容从一个方向插入或删除这个方向我们叫栈顶而从其他位置获取内容是不被允许的。栈最显著的特征就是 LIFOLast In, First Out后进先出。一个直观的例子栈就像是一个放书本的抽屉进栈的操作好比往抽屉里放一本书新进去的书永远在最上层而退栈则相当于从里往外拿书本永远是从最上层开始拿所以拿出来的永远是最后进去的那一本。栈的常用操作与复杂度栈的四种基本操作进栈 - push - 将元素放置到栈顶退栈 - pop - 将栈顶元素弹出栈顶 - top - 得到栈顶元素的值是否空栈 - isEmpty - 判断栈内是否有元素。由于栈只在尾部操作用数组模拟很容易达到 O(1) 的时间复杂度当然也可以用链表实现即链式栈进栈 - O(1)出栈 - O(1)。栈的典型应用函数调用栈浏览器前进后退匹配括号单调栈用来寻找下一个更大更小元素。本仓库中与栈直接相关的练习题目包括 394. 字符串解码、946. 验证栈序列对应仓库中的 validate-stack-sequences以及 1381. 设计一个支持增量操作的栈。在仓库中还可以找到栈与队列专题的更多资料参见 thinkings/basic-data-structure.md。单调栈的定义与判定什么是单调栈单调栈是一种特殊的栈。栈本来就是一种受限的数据结构单调栈在此基础上又受限了一次受限单调栈要求栈中的元素是单调递增的或者单调递减的。是否严格递增或递减可以根据实际情况来确定。这里用[a,b,c]表示一个栈其中左侧为栈底右侧为栈顶。单调增还是单调减取决于出栈顺序如果出栈的元素是单调增的那就是单调递增栈如果出栈的元素是单调减的那就是单调递减栈。例如[1,2,3,4]是一个单调递减栈出栈顺序是 4321[3,2,1]是一个单调递增栈出栈顺序是 123[1,3,2]不是一个合法的单调栈出栈顺序 231 不单调。注意栈内元素的递增/递减与栈的单调递增/单调递减命名取决于出栈顺序这是初学者最容易混淆的地方。从栈底到栈顶看[1,2,3,4]是递增的但因为出栈是 4→3→2→1 递减所以它叫单调递减栈反之[3,2,1]从栈底到栈顶递减出栈却是 1→2→3 递增因此叫单调递增栈。仓库内 problems/1019.next-greater-node-in-linked-list.md 也给出了同样的定义单调栈即满足单调性的栈结构与单调队列相比其只在一端进行进出将一个元素插入单调栈时为了维护栈的单调性需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。适用场景单调栈适合的题目是求解下一个大于 xxx或者下一个小于 xxx这种题目。当你遇到这种需求时就应该想到单调栈。那么为什么单调栈适合这类题目下面通过一个单调递减栈的完整推演来说明。单调栈核心推演以单调递减栈为例我们需要依次将数组[1,3,4,5,2,9,6]压入单调栈首先压入 1此时栈为[1]继续压入 3此时栈为[1,3]继续压入 4此时栈为[1,3,4]继续压入 5此时栈为[1,3,4,5]如果继续压入 2此时栈为[1,3,4,5,2]不满足单调递减栈的特性因此需要调整。由于栈只有 pop 操作我们只好不断 pop直到满足单调递减为止实际上我们并没有直接压入 2而是先 poppop 到压入 2 依然可以保持单调递减再压入 2此时栈为[1,2]继续压入 9此时栈为[1,2,9]如果继续压入 6则不满足单调递减栈的特性故技重施不断 pop直到满足单调递减为止此时栈为[1,2,6]。注意第 6 步和第 8 步结束后栈仍然是非空的。如果有的题目需要用到所有数组的信息那么很有可能因为没考虑边界而不能通过所有的测试用例。这里介绍一个技巧——哨兵法这个技巧经常用在单调栈的算法中。哨兵法Sentinel对于上面的例子可以在原数组[1,3,4,5,2,9,6]的右侧添加一个小于数组中最小值的项比如 -1此时数组变为[1,3,4,5,2,9,6,-1]。这样在遍历结束时栈中所有剩余元素都会被触发弹出从而计算出每个元素对应的答案无需在遍历结束后再单独处理栈内残留元素。这种技巧可以简化代码逻辑建议尽量掌握。哨兵法在本仓库的实战题解中有更充分的体现problems/84.largest-rectangle-in-histogram.md 的单调栈解法在heights首尾各添加了一个 0 作为哨兵为了统一算法逻辑减少边界处理我在 heights 首尾添加了两个哨兵元素这样我们可以保证所有的柱子都会出栈。 文末还专门解释了哨兵的作用末尾的哨兵是为了将栈清空防止遍历完成栈中还有没参与运算的数据前面的哨兵则是防止st[-1]越界。可见哨兵法既解决栈非空的收尾问题也解决访问栈内元素的越界问题。为什么单调栈能求出下一个更小/更大的位置上面的例子推演完就不难理解单调栈为何适合下一个大于/小于 xxx类题目了。以在其之后第一个小于其本身的位置为例3 的索引是 1其后第一个小于 3 的索引是 42 的索引是 4其后第一个小于 2 的索引在索引 0但它在 2 之前不符合条件即不存在在 2 之后第一个小于 2 本身的位置第 6 步开始 pop第一个被 pop 出来的是 5因此 5 之后第一个小于 5 的索引是 4同理被 pop 出来的 3、4、5 的答案也都是 4第 8 步 pop 出来的是 9因此 9 之后第一个小于 9 的索引是 6。如果用ans表示在其之后第一个小于其本身的位置ans[i]表示arr[i]之后第一个小于arr[i]的位置ans[i]为 -1 表示这样的位置不存在如前文的 2那么此时的ans是[-1,4,4,4,-1,-1,-1]。这个算法的过程用一句话总结就是如果压栈之后仍然可以保持单调性那么直接压否则先弹出栈的元素直到压入之后可以保持单调性。这个算法的原理用一句话总结就是被弹出的元素都是大于当前元素的并且由于栈是单调的因此在其之后小于其本身的最近的那个元素就是当前元素。通用模板伪代码与双语言实现伪代码模板上面的算法可以用如下伪代码表示同时这是一个通用的算法模板遇到单调栈的题目可以直接套用。建议大家用自己熟悉的编程语言实现一遍以后改改符号基本就能用。class Solution: def monostoneStack(self, arr: List[int]) - List[int]: stack [] ans 定义一个长度和 arr 一样长的数组并初始化为 -1 循环 i in arr: while stack and arr[i] arr[栈顶元素]: peek 弹出栈顶元素 ans[peek] i - peek stack.append(i) return ans复杂度分析时间复杂度由于arr的元素最多只会入栈、出栈一次因此时间复杂度仍然是 O(N)其中 N 为数组长度空间复杂度由于使用了栈并且栈的长度最大和arr长度一致因此空间复杂度是 O(N)其中 N 为数组长度。Python3 模板class Solution: def monostoneStack(self, T: List[int]) - List[int]: stack [] ans [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: peek stack.pop(-1) ans[peek] i - peek stack.append(i) return ansJavaScript 模板var monostoneStack function (T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while (stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };两个模板的结构完全一致差异只在语言语法上Python 通过T[i] T[stack[-1]]判断是否触发弹出求下一个更大JS 通过T[stack[stack.length - 1]] T[i]表达同一逻辑注意模板栈中存的是下标而非元素值这样i - peek才能直接算出距离。模板使用要点当题目要求下一个更大元素时使用单调递减栈如上面模板元素从大到小维护遇到更大值触发弹出当题目要求下一个更小元素时把比较符号反过来即可。严格单调与否还是取决于题目对相等元素的处理要求。源码级实战模板如何落到经典题目739. 每日温度模板的直接套用每日一题 739.Daily Temperatures 是单调栈最典型的入门题给定每日温度列表T返回一个列表对每一天说明要等多少天才能等到更暖和的温度若不存在则填 0。暴力解法是双层 for 循环时间复杂度 O(n²)而用单调递减栈一次遍历即可var dailyTemperatures function(T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while(stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };该题解的 Python3 版本与上面的模板逐行对应class Solution: def dailyTemperatures(self, T: List[int]) - List[int]: stack [] ans [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: peek stack.pop(-1) ans[peek] i - peek stack.append(i) return ans对比可见单调栈模板的本质就是遍历一遍 维护单调性 弹出时结算答案题目变了模板的骨架不变变化的只是结算逻辑。时间复杂度 O(n)、空间复杂度 O(n)。84. 柱状图中最大的矩形哨兵法的完整示范problems/84.largest-rectangle-in-histogram.md 是单调栈的经典难题。题目要求给定 n 个非负整数表示柱状图中各个柱子的高度每个柱子相邻且宽度为 1求能勾勒出的矩形最大面积如输入[2,1,5,6,2,3]输出 10。题解指出暴力枚举左右端点法O(N²)会 TLE优化的核心是求每个柱子左边第一个比它小的位置和右边第一个比它小的位置——这正是单调栈最擅长的场景。核心结论对于栈顶元素其右边第一个小于它的就是当前遍历到的柱子左边第一个小于它的就是栈中下一个要被弹出的元素因此以当前栈顶为最小柱子的面积为高度 × (当前遍历到的柱子索引 - 栈中下一个要被弹出的元素索引 - 1)。单调栈解法Python在首尾添加哨兵 0保证所有柱子都会出栈class Solution: def largestRectangleArea(self, heights: List[int]) - int: n, heights, st, ans len(heights), [0] heights [0], [], 0 for i in range(n 2): while st and heights[st[-1]] heights[i]: ans max(ans, heights[st.pop(-1)] * (i - st[-1] - 1)) st.append(i) return ans这里的面积公式(i - st[-1] - 1)与模板中的距离公式i - peek同源都是从弹出时结算的框架衍生出来的首尾两个哨兵 0 则完整示范了前文讲的哨兵法既保证栈被清空又避免st[-1]越界。42. 接雨水单调栈与双数组、双指针的对比problems/42.trapping-rain-water.md 以[0,1,0,2,1,0,1,3,2,1,2,1]为例输出可接 6 个单位雨水。题解提供了三种递进思路前置知识明确包含单调栈双数组法建模h[i] min(左边柱子最大值, 右边柱子最大值)用leftMax、rightMax两个数组时间复杂度 O(N)、空间复杂度 O(N)双指针法只关心左右两侧较小的那一个一次遍历维护左右最大值时间复杂度 O(N)、空间复杂度 O(1)单调栈法用于寻找下一个更大元素场景逐出栈时累计积水。这道题的价值在于同一个问题存在多种解法单调栈只是其一学习时应能区分每种解法的空间/时间权衡。仓库中还有 85. 最大矩形 进一步演示了如何把 84 题的单调栈解法封装成 API逐行扫描矩阵得到heights数组后复用将二维问题化为一维柱状图问题。更多练习题目下面几个题能帮助你进一步理解单调栈并明白什么时候可以用单调栈进行算法优化42. 接雨水84. 柱状图中最大的矩形739. 每日温度85. 最大矩形1019. 链表中的下一个更大节点题解明确指出看完题目就应该想到单调栈才行……使用单调栈可以将时间复杂度降低到线性456. 132 模式题解使用单调栈 从右往左遍历求最大的小于当前数的 2去除重复字母移掉 K 位数字下一个更大元素 I最短无序连续子数组股票价格跨度仓库中其他涉及单调栈的题解还包括 239. 滑动窗口最大值、768. 最多能完成排序的块 II、975. 奇偶跳 等可在 problems 目录下继续检索。若想系统地按专题刷题可以参考 thinkings/README.md 中的专题索引以及 91 天学算法 的细化整理。总结单调栈本质就是栈而栈本身就是一种受限的数据结构其受限指的是只能在一端进行操作单调栈在栈的基础上进一步受限即要求栈中的元素始终保持单调性。由于栈中的元素是单调的因此它天生适合解决在其之后第一个小于或大于其本身的位置这类题目。当你遇到题目需要找下一个更大/更小元素时就可以考虑使用单调栈。单调栈的写法相对比较固定可以参照本文的伪代码模板自己总结一份模板以后直接套用可以大大提高做题效率和容错率。回顾全文几个核心要点值得反复咀嚼单调性的判定看的是出栈顺序而非从栈底到栈顶的顺序栈中存下标便于直接计算距离差i - peek弹出时结算是模板的灵魂答案在元素被弹出那一刻产生哨兵法在数组尾部/首部添加极值哨兵统一边界逻辑避免栈残留与越界比较符号与严格性/、/随题目对下一个更大/更小、相等如何处理的要求调整。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考