LeetCode 单调栈专题精讲：原理、通用模板与实战题解-港品优选

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 通用模板。

栈：单调栈的基础

栈的定义与特征

顾名思义，单调栈首先是一种栈，因此要学单调栈，首先要彻底搞懂栈。栈是一种受限的数据结构，体现在只允许新的内容从一个方向插入或删除，这个方向我们叫栈顶，而从其他位置获取内容是不被允许的。栈最显著的特征就是 LIFO（Last 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]是一个单调递减栈（出栈顺序是 4，3，2，1）；
[3,2,1]是一个单调递增栈（出栈顺序是 1，2，3）；
[1,3,2]不是一个合法的单调栈（出栈顺序 2，3，1 不单调）。

注意：栈内元素的"递增/递减"与栈的"单调递增/单调递减"命名取决于出栈顺序，这是初学者最容易混淆的地方。从栈底到栈顶看，[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，而是先 pop，pop 到压入 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 的索引是 4；
2 的索引是 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 ans

JavaScript 模板

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数组后复用，将二维问题化为一维柱状图问题。

总结

单调栈本质就是栈，而栈本身就是一种受限的数据结构，其受限指的是只能在一端进行操作；单调栈在栈的基础上进一步受限，即要求栈中的元素始终保持单调性。

由于栈中的元素是单调的，因此它天生适合解决"在其之后第一个小于（或大于）其本身的位置"这类题目。当你遇到题目需要找"下一个更大/更小元素"时，就可以考虑使用单调栈。

单调栈的写法相对比较固定，可以参照本文的伪代码模板自己总结一份模板，以后直接套用可以大大提高做题效率和容错率。回顾全文，几个核心要点值得反复咀嚼：

单调性的判定看的是出栈顺序，而非从栈底到栈顶的顺序；
栈中存下标，便于直接计算距离差i - peek；
弹出时结算是模板的灵魂，答案在元素被弹出那一刻产生；
哨兵法（在数组尾部/首部添加极值哨兵）统一边界逻辑，避免栈残留与越界；
比较符号与严格性（>/>=、</<=）随题目对"下一个更大/更小、相等如何处理"的要求调整。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

企业官网建设流程全解析