栈与队列的核心理解#

什么是栈#

栈是一种 后进先出（LIFO, Last In First Out）的数据结构。最后放进去的元素，最先被拿出来。

最常见的几个动作是：

push：压栈
pop：弹栈
top / peek：查看栈顶

栈的直觉非常像一摞盘子。你只能从最上面继续放，也只能从最上面拿。

刷题里，栈最常用于解决下面几类问题：

配对与匹配，比如括号匹配
撤销、回退、消消乐
表达式求值
单调栈维护"下一个更大/更小元素"

什么是队列#

队列是一种 先进先出（FIFO, First In First Out）的数据结构。最先进入队列的元素，会最先离开。

常见动作是：

push / offer：入队
pop / poll：出队
front / peek：查看队头

队列非常像排队买饭。先来的人先处理，后来的只能排在后面。

刷题里，队列最常用于：

按顺序处理元素
层序遍历
BFS 最短步数问题
滑动窗口
单调队列维护窗口最值

栈和队列的区别#

最核心的区别其实只有一句话：

栈：后进先出
队列：先进先出

也正因为这个区别，它们擅长处理的问题也不同：

栈更擅长"最近的、嵌套的、需要回退的"关系
队列更擅长"按到达顺序逐个处理"的关系

所以很多题目不是在考你会不会写 append 和 pop，而是在考你：

1
这个问题需要的是最近进入的元素，还是最早进入的元素？

什么情况下想到栈#

看到下面这些特征，优先想栈：

括号匹配、标签匹配、路径回退
撤销、恢复、消消乐、相邻抵消
表达式求值
需要维护"最近一个比当前大/小"的元素
需要在扫描过程中保存"还没处理完的历史信息"

一句话记忆：

1
只要题目和“最近的未完成状态”有关，就很容易想到栈。

什么情况下想到队列#

看到下面这些味道，优先想队列：

层序遍历
按轮次推进
最少步数、最短操作次数
数据流按顺序进入，旧元素会自然淘汰
滑动窗口

一句话记忆：

1
只要题目强调“顺序推进、一层一层扩散、最先进入最先处理”，就很容易想到队列。

Python 中的栈、队列、双端队列、优先队列#

Python 里最常用的几个容器如下：

普通栈：直接用 list
普通队列 / 双端队列：用 collections.deque
优先队列：用 heapq

其中：

list.append() + list.pop() 就可以当栈用
deque.append() / deque.popleft() 很适合写队列
heapq 默认是小根堆，如果想模拟大根堆，通常存相反数

刷题时其实不用纠结"我是不是在手写一个正式数据结构"，更重要的是：

1
我现在需要维护哪种顺序？

基础栈题：后进先出#

括号匹配#

LC20 - 有效的括号#

这是最基础的栈应用题，我们只需要用一个栈来决定就行。首先用字典记录右括号对应的左括号，右括号遇到左括号必须弹出，不然就是无效的，最后栈非空也是无效。

Python3 点击展开代码

12 lines 展开代码

def isValid(self, s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []

    for ch in s:
        if ch not in pairs:
            stack.append(ch)
            continue
        if not stack or stack.pop() != pairs[ch]:
            return False

    return not stack

如果只有一种括号，那么有另外一种思路，用左括号数量去判断有效性。如果要让字符串有效，那么必须每个右括号 ) 的左边必须有一个左括号 ( 和它匹配。所以我们维持一个变量left，遇到左括号+，遇到右括号-，这样中间是否会右括号太多以及最后只要判断是不是正好抵消就行。（其实与栈思路一样，只不过只用了一个变量）。本题不行，因为有三种括号，所以要加大统计量。

LC921 - 使括号有效的最少添加#

只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号
例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。返回为使结果字符串 s 有效而必须添加的最少括号数。

这一题可以回到需求的解法了，我们维持插入次数res、右括号的需求量need。如果是左括号，need+1即可；如果是右括号，我们不仅要-1，还要判断-1是不是变成刚需左括号了，如果是这样必须立刻补左括号，res+1。这样，我们最终返回res+need就是需要插入的总次数。

总而言之，我们在插入过程中维持有效性。

Python3 点击展开代码

12 lines 展开代码

def minAddToMakeValid(self, s: str) -> int:
    res = 0
    need = 0
    for ch in s:
        if ch == '(':
            need += 1
        if ch == ')':
            need -= 1
            if need == -1:
                res += 1
                need += 1
    return res + need

LC1541 - 平衡括号字符串的最少插入次数#

本题和上一题的区别在于，一个left要对应两个右括号了，简单改一下就能出答案。

Python3 点击展开代码

19 lines 展开代码

def minInsertions(self, s: str) -> int:
    res = 0
    need = 0

    for ch in s:
        if ch == '(':
            # 当右括号需求为奇数，需要插入一个右括号到这个左括号前面，避免前面不匹配了。
            if need % 2 == 1:
                res += 1
                need -= 1
            # 插入一个左括号
            need += 2
        else:
            need -= 1
            if need == -1:
                res += 1
                need = 1

    return res + need

LC1249 - 移除无效的括号#

这题要求从一个字符串中删除最小数量的括号，让括号有效。字符串中有一些无关小写字母。按照LC20相同的代码，其实我们就可以直接得到需要删除的个数，但是本题要求的是删除后的字符串，需要更多信息。但是其实改动也不多。

Python3 点击展开代码

24 lines 展开代码

def minRemoveToMakeValid(self, s: str) -> str:
    ans = []
    balance = 0  # 当前 ans 里还没匹配掉的 '(' 个数

    for ch in s:
        if ch == '(':
            ans.append(ch)
            balance += 1
        elif ch == ')':
            if balance == 0:
                continue
            ans.append(ch)
            balance -= 1
        else:
            ans.append(ch)

    res = []
    for ch in reversed(ans):
        if ch == '(' and balance > 0:
            balance -= 1
            continue
        res.append(ch)

    return ''.join(reversed(res))

这一题，当然也可以用栈存待会要删除的下标（只存还没匹配的 ( 的下标），来之后构造答案，思路很自然：

Python3 点击展开代码

17 lines 展开代码

def solution(s: str) -> str:
    stack = []
    chars = list(s)

    for i, ch in enumerate(chars):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()
            else:
                chars[i] = ''

    while stack:
        chars[stack.pop()] = ''

    return ''.join(chars)

综上，结构匹配型我们就用栈来做，数量欠账类的用res/need，构造答案则是两者皆可，用栈来存储更优雅。

表达式与字符串处理#

LC150 - 逆波兰表达式求值#

逆波兰式式经典应用栈求数值的题目。

Python3 点击展开代码

20 lines 展开代码

def evalRPN(self, tokens: list[str]) -> int:
    stack = []

    for ch in tokens:
        if ch not in {'+', '-', '*', '/'}:
            stack.append(int(ch))
        else:
            a = stack.pop()
            b = stack.pop()

            if ch == '+':
                stack.append(b + a)
            elif ch == '-':
                stack.append(b - a)
            elif ch == '*':
                stack.append(b * a)
            else:
                stack.append(int(b / a))

    return stack[-1]

LC71 - 简化路径#

我们通过curr_name来判断目前两个/直接夹的东西，并采用对应的栈操作。

Python3 点击展开代码

20 lines 展开代码

def simplifyPath(self, path: str) -> str:
    stack = []
    # 核心，用来缓冲目前名称
    curr_name=""
    # 末尾添加 / 保证全部出栈
    for ch in path +'/':
        if ch == '/':
            # 如果是..则出栈
            if curr_name=="..":
                if stack:
                    stack.pop()
            # 如果不是废话（空或者.），压栈
            elif curr_name !="" and curr_name!=".":
                stack.append(curr_name)
            # 缓冲部分清空
            curr_name = ""
        # 接下来是普通字符，简单入栈
        else:
            curr_name+=ch
    return "/"+"/".join(stack)

LC227 - 基本计算器 II#

这一题，其实是中缀表达式求值，上一题的逆波兰表达式则是后缀表达式。后缀表达式可以轻松用栈解决，中缀则是可以通过栈来转为后缀。思路如下：

遇到操作数直接加入后缀表达式
遇到左括号直接入栈，然后遇到右括号依次弹出栈内运算符并加入后缀表达式，直到弹出 ( 为止。
遇到运算符，则比较栈顶的运算符的优先级，如果比栈顶优先级高/栈顶为 ( /栈为空，则直接加入表达式；否则将栈顶弹出加入表达式，然后重新判断。
重复直到遍历完毕，将栈所有元素弹出，加入后缀表达式

不过对于本题来说，并不存在括号，我们可以这样来处理：遇到加减立刻将数字（取反）压栈，遇到乘除则立刻和栈顶计算：

Python3 点击展开代码

24 lines 展开代码

def calculate(self, s: str) -> int:
    stack = []
    num = 0
    sign = '+'

    for i, ch in enumerate(s):
        # 多位数字
        if ch.isdigit():
            num = num * 10 + int(ch)

        if ch in '+-*/' or i == len(s) - 1:
            if sign == '+':
                stack.append(num)
            elif sign == '-':
                stack.append(-num)
            elif sign == '*':
                stack.append(stack.pop() * num)
            elif sign == '/':
                stack.append(int(stack.pop() / num))

            sign = ch
            num = 0

    return sum(stack)

为什么可以这么做？这是因为，我们用栈调整了运算顺序。如果是优先级较低的+-，我们先记账，留到最后一起加减；如果是乘除，我们就立刻运算。

LC224 - 基本计算器#

这一题属于有括号，但只有+-。因此，也是有简化的方式：我们不用处理优先级，只需要看看这一层算到了多少、这一层整体前面带的符号是什么。

用res记录当前层结果
sign记录当前数字前的符号
num组装多位数
遇到 ( 将外层res和sign压栈，进入新的一层
遇到 ) 先结算当前层，再和外层合并

Python3 点击展开代码

29 lines 展开代码

def calculate(self, s: str) -> int:
    stack = []
    res = 0
    num = 0
    sign = 1

    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == '+':
            res += sign * num
            num = 0
            sign = 1
        elif ch == '-':
            res += sign * num
            num = 0
            sign = -1
        elif ch == '(':
            stack.append(res)
            stack.append(sign)
            res = 0
            sign = 1
        elif ch == ')':
            res += sign * num
            num = 0
            res *= stack.pop()
            res += stack.pop()

    return res + sign * num

LC772 - 基本计算器 III#

这一题，不仅有括号，且有+-*/，没有什么比较好的方法遍历一次解决了。一般而言，我们可以用栈按照前面的技巧转为后缀表达式，然后用栈计算答案。但是，这一题更好的写法是"递归+栈"，也就是每一层递归只处理一层的表达式，遇到 ( 就递归进去，拿子表达式的结果当成一个普通数字 num 来继续算。

所以其实这一题可以根据基本计算器 II 加一个递归入口简单改编出来。

Python3 点击展开代码

27 lines 展开代码

from collections import deque

def calculate(self, s: str) -> int:
    def dfs(q):
        num, sign, stk = 0, "+", []
        while q:
            c = q.popleft()
            if c.isdigit():
                num = num * 10 + int(c)
            if c == "(":
                num = dfs(q)
            if c in "+-*/)" or not q:
                match sign:
                    case "+":
                        stk.append(num)
                    case "-":
                        stk.append(-num)
                    case "*":
                        stk.append(stk.pop() * num)
                    case "/":
                        stk.append(int(stk.pop() / num))
                num, sign = 0, c
            if c == ")":
                break
        return sum(stk)

    return dfs(deque(s))

辅助栈与模拟栈#

LC155 - 最小栈#

最小栈是一种支持push、pop、top操作，并能在常数时间内检索到最小元素的栈，一般的解决思路是用两个栈来实现，一个栈stack来保存元素，然后用另一个栈min_stack[i] 表示主栈 stack[0..i] 这一层时的最小值：

Python3 点击展开代码

27 lines 展开代码

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        # 最小栈为空或者新值不大于旧栈顶
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        # 否则将最小值再次入栈
        else:
            self.min_stack.append(self.min_stack[-1])
        self.stack.append(val)

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()
        if self.min_stack:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]
        

    def getMin(self) -> int:
        return self.min_stack[-1]

LC232 - 用栈实现队列#

又是数据设计题，我们可以用两个栈来模拟队列，其中一个是常规栈，另一个用于出栈倒腾顺序：

Python3 点击展开代码

25 lines 展开代码

class MyQueue:
    # 两个栈屁股对屁股实现
    def __init__(self):
        self.st1=[]
        self.st2=[]

    def push(self, x: int) -> None:
        # 入栈操作笔记普通，就是进st1
        self.st1.append(x)

    def pop(self) -> int:
        # 出栈先把st1全倒进st2，然后再出
        # 先调用peek作为前置操作，倒栈写在那里
        self.peek()
        return self.st2.pop()

    def peek(self) -> int:
        if not self.st2:
            # 把 st1 元素压入 st2
            while self.st1:
                self.st2.append(self.st1.pop())
        return self.st2[-1]       

    def empty(self) -> bool:
        return not self.st1 and not self.st2

LC225 - 用队列实现栈#

用两个队列来实现栈，思路如下：

push(x)：直接进主队列
pop()：把前 n-1 个元素转移到辅助队列，最后剩下的那个就是栈顶，弹出它
操作结束后交换 q1 和 q2，让 q1 继续做主队列

Python3 点击展开代码

31 lines 展开代码

from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        # q1正常入队
        self.q1.append(x)

    def pop(self) -> int:
        # 出队前倒腾顺序
        while len(self.q1)>1:
            self.q2.append(self.q1.popleft())
        ans = self.q1.popleft()
        self.q1,self.q2 = self.q2, self.q1
        return ans

    def top(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        ans = self.q1.popleft()
        # 多了一句元素归还q2，因为我们不需要真弹出
        self.q2.append(ans)
        self.q1, self.q2 = self.q2, self.q1
        return ans

    def empty(self) -> bool:
        return not self.q1

基础队列题：先进先出#

普通队列#

LC933 - 最近的请求次数#

本题只记录和目前时间差3000以内的数目，所以我们可以直接用一个队列维护，如果队头和入队元素差距超过3000，直接弹出：

Python3 点击展开代码

9 lines 展开代码

class RecentCounter:
    def __init__(self):
        self.q=deque()

    def ping(self, t: int) -> int:
        self.q.append(t)
        while t-self.q[0]>3000:
            self.q.popleft()
        return len(self.q)

LC649 - Dota2 参议院#

本题是一个轮流禁言题，也就是循环回合 + 先手淘汰。按照原始顺序流动，每个 R 可以禁言一个 D，每个 D 可以禁言一个 R，直到最后只剩同一阵容胜利。

这一题最好的解法是用两个队列存储还活着的议员下标，然后每次队头下标小的先行动，把对方队头ban掉，然后把自己的下标加上n放到队尾（等下一轮），被ban掉的出队就不会再回来了。

Python3 点击展开代码

23 lines 展开代码

from collections import deque

def predictPartyVictory(self, senate: str) -> str:
    n = len(senate)
    r_queue = deque()
    d_queue = deque()

    for i, ch in enumerate(senate):
        if ch == 'R':
            r_queue.append(i)
        else:
            d_queue.append(i)

    while r_queue and d_queue:
        r = r_queue.popleft()
        d = d_queue.popleft()

        if r < d:
            r_queue.append(r + n)
        else:
            d_queue.append(d + n)

    return "Radiant" if r_queue else "Dire"

双端队列#

LC641 - 设计循环双端队列#

这一题在 408 里也很常见。我们需要维持一个 front 和一个 rear，把数组想象成一个环，然后对这个环做入队、出队和取模移动。

Python3 点击展开代码

49 lines 展开代码

class MyCircularDeque:

    def __init__(self, k: int):
        self.capacity = k + 1
        self.q = [0] * self.capacity
        self.front = 0
        self.rear = 0

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.front = (self.front - 1 + self.capacity) % self.capacity
        self.q[self.front] = value
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.q[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1 + self.capacity) % self.capacity
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[self.front]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[(self.rear - 1 + self.capacity) % self.capacity]

    def isEmpty(self) -> bool:
        return self.front == self.rear

    def isFull(self) -> bool:
        return (self.rear + 1) % self.capacity == self.front

层序遍历与 BFS#

队列常被用来实现层序遍历，所以这一组题也很适合放在这里一起理解。

LC102 - 二叉树的层序遍历#

经典层序遍历，需要达到肌肉级别记忆。

Python3 点击展开代码

25 lines 展开代码

from collections import deque

class TreeNode:
    def __init__(self,val =0 ,left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(self, root: TreeNode) -> list[list[int]]:
    if not root:
        return []
    q = deque([root])
    ans = []
    while q:
        sz = len(q)
        level = []
        for _ in range(sz):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        ans.append(level)
    return ans

LC107 - 二叉树的层序遍历 II#

自底向上的层序遍历，和上一题相比只是 ans 改成从左边添加而已。

Python3 点击展开代码

21 lines 展开代码

from collections import deque

def levelOrderBottom(self, root: TreeNode) -> list[list[int]]:
    if not root:
        return []

    q = deque([root])
    ans = deque()

    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        ans.appendleft(level)

    return list(ans)

LC103 - 二叉树的锯齿形层序遍历#

我们可以根据ans的长度得到奇数层偶数层，从而决定这个level是append还是appendleft。

Python3 点击展开代码

34 lines 展开代码

from collections import deque

class TreeNode:
    def __init__(self,val =0 ,left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(self, root: TreeNode) -> list[list[int]]:
    if not root:
        return []
    q = deque([root])
    ans = []
    while q:
        sz = len(q)
        level = deque()
        if len(ans)%2 == 0:
            for _ in range(sz):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        else:
            for _ in range(sz):
                node = q.popleft()
                level.appendleft(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)            
        ans.append(list(level))
    return ans

LC199 - 二叉树的右视图#

右视图其实就是每层的最后一个节点，所以在普通层序遍历的基础上，取每个 level[-1] 即可。这题和前面几题的差别不在数据结构，而在"每层要收集哪一个元素"。

图论中的队列#

LC994 - 腐烂的橘子#

本题用队列来存储腐烂橘子的坐标，弹出的时候让周围的新鲜橘子入队，每层扩散一次，时间 +1。当队列为空时遍历结束，这时候如果还有新鲜橘子就不可能全部腐烂，返回 -1，否则返回分钟数。

Python3 点击展开代码

32 lines 展开代码

from collections import deque

def orangesRotting(self, grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    q = deque()
    fresh = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                q.append((i, j))
            elif grid[i][j] == 1:
                fresh += 1

    if fresh == 0:
        return 0

    minutes = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q and fresh > 0:
        for _ in range(len(q)):
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh -= 1
                    q.append((nx, ny))
        minutes += 1

    return minutes if fresh == 0 else -1

LC752 - 打开转盘锁#

这一题的目标是最少步数，所以应该用BFS来做，因为BFS是天然的求"无权路最短图"的方法。如果用DFS，会一路走到底，然后要保证路径最短，还要将所有可能路径搜完，再取最小值，复杂度很差，且存在大量重复状态。

我们用bfs的次数就可以统计进行的步数，所以这一题只要把握好状态更新入队即可。

Python3 点击展开代码

36 lines 展开代码

from collections import deque

class Solution:
    def update(self, old: str, i: int) -> tuple[str, str]:
        s1 = list(old)
        s2 = list(old)
        num = int(old[i])
        s1[i] = str((num + 9) % 10)
        s2[i] = str((num + 1) % 10)
        return ''.join(s1), ''.join(s2)

    def openLock(self, deadends: list[str], target: str) -> int:
        visited = set(deadends)
        if '0000' in visited:
            return -1

        q = deque(['0000'])
        visited.add('0000')
        depth = 0

        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur == target:
                    return depth

                for i in range(4):
                    s1, s2 = self.update(cur, i)
                    for state in (s1, s2):
                        if state not in visited:
                            visited.add(state)
                            q.append(state)

            depth += 1

        return -1

LC773 - 滑动谜题#

依旧状态更新，依旧最短次数。我们直接一个广搜，用队列存储更新状态。可是，如果每次队列都存储一个二维数组，负担太大了，而且由于我们已经知道是2x3的板子了，可以先预处理好可以相邻下标。

Python3 点击展开代码

50 lines 展开代码

from collections import deque
class Solution:
    # 我们需要先预处理一个邻居表，用于状态转移
    # 一下分别是2x3板子中，0-5对应的相邻索引
    mapping = [
        [1,3],
        [0,4,2],
        [1,5],
        [0,4],
        [3,1,5],
        [4,2]
    ]

    # 辅助函数，交换元素
    def update_status(self,old,i,j):
        new = old[:]
        new[i], new[j] = new[j], new[i]
        return new

    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # BFS不仅是寻路算法，也是一种暴力搜索算法，暴力穷举的问题BFS都可以用
        target = [1,2,3,4,5,0]
        start = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                start.append(board[i][j])

        q = deque()
        visited = set()
        # 从起点BFS开始搜索
        q.append(start)
        visited.add(tuple(start))

        step = 0
        while q:
            sz = len(q)
            for _ in range(sz):
                cur = q.popleft()
                if cur == target:
                    return step
                # 如果不是目标，将所以可能的转移状态写入
                zero_idx = cur.index(0)
                for to_swap in self.mapping[zero_idx]:
                    new = self.update_status(cur,zero_idx,to_swap)
                    if tuple(new) not in visited:
                        q.append(new)
                        visited.add(tuple(new))
            # 一个更新结束（bfs层）
            step += 1
        return -1

单调栈：维护下一个更大或更小#

单调栈的核心思想#

单调栈本质上还是栈，只不过我们在压栈时额外维护了一个"单调性"：

要么从栈底到栈顶单调递增
要么从栈底到栈顶单调递减

它最擅长解决的问题是：

下一个更大元素
下一个更小元素
上一个更大 / 更小元素
左右第一个打破单调性的位置
区间贡献问题

很多人第一次学单调栈，会觉得它像魔法。其实它做的事情非常朴素：

1
新元素一来，就把那些已经不可能成为答案的旧元素弹掉。

所以单调栈的关键不在"背模板"，而在想清楚：

栈里到底存的是值还是下标
当前元素来了之后，谁已经失去资格了
弹栈的那一刻，我能不能顺便结算答案

下一个更大元素#

LC496 - 下一个更大元素 I#

要找下一个更大元素，单调栈就是非常自然的解法。我们可以用哈希表记录每个元素下一个更大元素。

Python3 点击展开代码

10 lines 展开代码

def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
    stack = []
    next_map = {}

    for num in nums2:
        while stack and stack[-1] < num:
            next_map[stack.pop()] = num
        stack.append(num)

    return [next_map.get(num, -1) for num in nums1]

LC503 - 下一个更大元素 II#

这一题要求 nums 中每个元素的下一个更大元素，但是本题数组是循环数组。这一题的解法实际上只要做两个处理：

让循环范围扩大确保每个元素都判断一次是否是下一个元素
然后让下标定位时取余即可

Python3 点击展开代码

12 lines 展开代码

def nextGreaterElements(self, nums: list[int]) -> list[int]:
    n = len(nums)
    ans = [-1] * n
    stack = []  # 存下标
    for i in range(2 * n):
        x = nums[i % n]
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        # 额外判断是不是第一次遍历，要不要加下标了
        if i < n:
            stack.append(i)
    return ans

LC739 - 每日温度#

一道很规整的单调栈题目，存下标，算距离存入。

Python3 点击展开代码

10 lines 展开代码

def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    ans = [0]*n
    st = []
    for i in range(n):
        while st and temperatures[st[-1]]<temperatures[i]:
            idx = st.pop()
            ans[idx] = i - idx
        st.append(i)
    return ans

找左右边界#

LC84 - 柱状图中最大的矩形#

本质上，也是在寻找左右两侧第一个比当前矩形矮的，然后这时候就可以得出当前矩形能贡献出来的最大矩形。

Python3 点击展开代码

12 lines 展开代码

def largestRectangleArea(self, heights: list[int]) -> int:
    heights = [0] + heights + [0]
    st = []
    max_S = 0
    for i,val in enumerate(heights):
        while st and st[-1][1]>val:
            _,curr_val = st.pop()
            left_idx = st[-1][0]
            right_idx = i
            max_S = max(max_S,(right_idx-left_idx-1)*curr_val)
        st.append((i,val))
    return max_S

LC85 - 最大矩形#

这一题，实际上是枚举每一行作为底边，来做多个一维柱状图最大矩形问题。

Python3 点击展开代码

35 lines 展开代码

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        heights = [0] + heights + [0]
        stack = []
        ans = 0

        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] > h:
                cur_h = heights[stack.pop()]
                left = stack[-1]
                width = i - left - 1
                ans = max(ans, cur_h * width)
            stack.append(i)

        return ans

    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        heights = [0] * cols
        ans = 0

        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == '1':
                    heights[j] += 1
                else:
                    # 如果有中断，就不能再计算
                    heights[j] = 0

            ans = max(ans, self.largestRectangleArea(heights))

        return ans

LC901 - 股票价格跨度#

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度。当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

这一题和普通"找下一个更大元素"的题有一点不一样。它不是一次性给完整数组，而是数据流在线输入，所以不能等全部输入完再统一求。

思路是维护一个单调递减栈，栈里存 (price, span)。如果当前价格比栈顶大，那么栈顶那一整段跨度都能被当前价格吞掉，于是我们把它们的跨度累加起来。这就是这一题看起来"多了一个累加量"的原因。

Python3 点击展开代码

13 lines 展开代码

class StockSpanner:

    def __init__(self):
        self.stack = []  # (price, span)

    def next(self, price: int) -> int:
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]

        self.stack.append((price, span))
        return span

单调栈变形#

LC853 - 车队#

这一题属于"排序 + 单调栈"的变形。把车按位置从左到右排序后，每辆车都有一个到终点的时间 time = (target - pos) / speed。如果后车到终点所需时间小于等于前车，那么它最终一定会追上前车，合并成同一个车队。

所以我们只需要维护一个单调的到达时间栈，能合并的就弹掉，最后栈里剩下的就是车队数量。

Python3 点击展开代码

9 lines 展开代码

def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
    cars=sorted(zip(position,speed))
    stack=[]
    for pos,spd in cars:
        time=(target-pos)/spd
        while stack and stack[-1]<=time:
            stack.pop()
        stack.append(time)
    return len(stack)

区间贡献问题#

LC907 - 子数组的最小值之和#

这一题如果直接暴力二重循环弄出所有子数组，会超时。所以必须要转化思路，核心思想是算每个 arr[i] 作为最小值时，能贡献多少个子数组。

实际上，我们依旧要回到单调栈的原本思想，我们要看 arr[i] 左边第一个比它小的位置、右边第一个小于等于它的位置在哪。left[i] = 从 i 往左，最多能选多少个起点；right[i] = 从 i 往右，最多能选多少个终点；那么，arr[i] 的贡献 = arr[i] * left[i] * right[i]。

比如，[3,1,2,4]，3左边没有更小的，所以左侧可选一个起点；右侧第一个小于等于它的是1，所以只能是[3]。而1左侧没有比它更小的，起点可以选3或者1，右侧是没有小于等于它的，可以选1、2、4，一共贡献 123 = 6。

Python3 点击展开代码

28 lines 展开代码

def sumSubarrayMins(self, arr: list[int]) -> int:
    # 思路是对每个数找左、右第一个比它小的。
    # left[i] = 从 i 往左，最多能选多少个起点。换言之，就是找到第一个比它小的，之间的都可以当做起点。
    n = len(arr)
    left = [0] * n 
    st = []
    for i in range(n):
        while st and arr[st[-1]] > arr[i]:
            st.pop()
        # 空栈说明arr[i]已经是最小的
        left[i] = i - st[-1] if st else i + 1
        st.append(i)

    # right[i] = 从 i 往右，最多能选多少个终点。由于左边没有等于，我们知道等于也是可以的，选一侧用等于。
    # 操作几乎和左边对称
    right = [0] * n
    st = []
    for i in range(n-1,-1,-1):
        while st and arr[st[-1]] >= arr[i]:
            st.pop()
        right[i] = st[-1] - i if st else n-i
        st.append(i)

    MOD = 10**9 + 7
    ans = 0
    for i in range(n):
        ans = (ans + arr[i]*left[i]*right[i])%MOD
    return ans

LC2104 - 子数组范围和#

返回所有连续子数组最小元素和最大元素差值，在上一题中，我们已经求过了最小值贡献，改一下不等于号方向就可以求最大值贡献了。然后，用最大值贡献-最小值贡献，就是本题的答案。

Python3 点击展开代码

42 lines 展开代码

def subArrayRanges(self, nums: list[int]) -> int:
    n = len(nums)
    left_min = [0] * n
    right_min = [0] * n
    left_max = [0] * n
    right_max = [0] * n
    
    # 开始四遍单调栈求解
    st = []
    for i in range(n):
        while st and nums[st[-1]]>nums[i]:
            st.pop()
        left_min[i] = i - st[-1] if st else i+1
        st.append(i)

    st = []
    for i in range(n):
        while st and nums[st[-1]]<nums[i]:
            st.pop()
        left_max[i] = i - st[-1] if st else i+1
        st.append(i)

    st = []
    for i in range(n-1,-1,-1):
        while st and nums[st[-1]]>=nums[i]:
            st.pop()
        right_min[i] = st[-1] - i if st else n-i
        st.append(i)

    st = []
    for i in range(n-1,-1,-1):
        while st and nums[st[-1]]<=nums[i]:
            st.pop()
        right_max[i] = st[-1] - i if st else n-i
        st.append(i)
    
    # 现在，用最大值贡献-最小值贡献
    ans = [0] * n 
    for i in range(n):
        ans[i] = nums[i]*left_max[i]*right_max[i] - nums[i]*left_min[i]*right_min[i]

    return sum(ans)

本题其实可以细细品味，包含着单调栈的核心思想。

单调栈模板#

最常见的三个模板其实可以这样记：

Python3 点击展开代码

7 lines 展开代码

# 1. 正向扫描，当前元素去结算前面的人
stack = []
for i, x in enumerate(nums):
    while stack and nums[stack[-1]] < x:
        idx = stack.pop()
        # 在这里结算 idx 的答案
    stack.append(i)

Python3 点击展开代码

7 lines 展开代码

# 2. 反向扫描，当前元素直接找自己的答案
stack = []
for i in range(len(nums) - 1, -1, -1):
    while stack and stack[-1] <= nums[i]:
        stack.pop()
    ans[i] = stack[-1] if stack else -1
    stack.append(nums[i])

Python3 点击展开代码

10 lines 展开代码

# 3. 左右边界模板
heights = [0] + heights + [0]
stack = []
for i, h in enumerate(heights):
    while stack and heights[stack[-1]] > h:
        cur = stack.pop()
        left = stack[-1]
        width = i - left - 1
        # 在这里结算 cur 的贡献
    stack.append(i)

单调队列：维护滑动窗口最值#

单调队列的核心思想#

单调队列本质上是 deque + 维护单调性。

和单调栈相比，它最大的不同在于：单调队列往往服务于滑动窗口。所以除了维护单调性，还要解决一个额外问题：

1
队头这个元素过期了吗？

于是单调队列的经典操作一般有两步：

新元素进来时，从队尾弹出所有"不如它"的元素
窗口左端移动时，判断队头是否已经滑出窗口

所以单调队列最擅长的就是：

滑动窗口最大值 / 最小值
窗口合法性判定
前缀和 + 最优左端点筛选

滑动窗口最值#

LC239 - 滑动窗口最大值#

这是单调队列最经典的使用题。我们用deque，保持队头始终是当前窗口的最大值，然后每次验证队头是否过期即可。

Python3 点击展开代码

19 lines 展开代码

from collections import deque

def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
    q = deque()
    ans = []
    for i,val in enumerate(nums):
        while q and nums[q[-1]] <= val:
            q.pop()
        q.append(i)

        # 判断过期
        if q[0] <= i - k:
            q.popleft()
        
        # 判断是否可以录用
        if i >= k - 1:
            ans.append(nums[q[0]])
        
    return ans

前缀和 + 单调队列#

LC862 - 和至少为 K 的最短子数组#

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的最短非空子数组，并返回该子数组的长度。如果不存在这样的子数组，返回 -1 。(子数组连续)

我们知道，要想求任意子数组的和，用前缀和就可以解决。这题不能使用滑动窗口，因为 LC862 里可能有负数。有负数时，窗口右扩后，和不一定变大；左缩后，和也不一定变小，所以普通双指针失效。

构造好前缀和之后，用单调队列维护一批最有希望成为左端点的前缀和下标。为了让和尽量大，我们让最小的前缀和始终保持在队顶，然后遍历的时候每次和当前 pre[i] 做差得到和，大于k之后，将ans更新为较小的坐标长度。

Python3 点击展开代码

16 lines 展开代码

from collections import deque
from itertools import accumulate

def shortestSubarray(self, nums: list[int], k: int) -> int:
    prefix = [0] + list(accumulate(nums))
    q = deque()
    n = len(nums)
    ans = n+1
    for i in range(n+1):
        while q and prefix[i] - prefix[q[0]] >= k:
            ans = min(ans,i-q.popleft())

        while q and prefix[q[-1]]>=prefix[i]:
            q.pop()
        q.append(i)
    return ans if ans<=n else -1

这一题代码虽然很短，但思路转化并不直观，所以一定要把"前缀和 + 单调队列"的套路记住。

LC1438 - 绝对差不超过限制的最长连续子数组#

依旧是滑动窗口最值，这次既要最大又要最小，那么好，用两个队列就可以满足。

这一题包含比较通用的滑动窗口最值求解，请仔细阅读：

Python3 点击展开代码

26 lines 展开代码

def longestSubarray(self, nums: list[int], limit: int) -> int:
    max_q = deque()
    min_q = deque()
    left = 0
    ans = 0

    for right, x in enumerate(nums):
        while max_q and nums[max_q[-1]] <= x:
            max_q.pop()
        max_q.append(right)

        while min_q and nums[min_q[-1]] >= x:
            min_q.pop()
        min_q.append(right)

        # 过期机制
        while nums[max_q[0]] - nums[min_q[0]] > limit:
            if max_q[0] == left:
                max_q.popleft()
            if min_q[0] == left:
                min_q.popleft()
            left += 1

        ans = max(ans, right - left + 1)

    return ans

单调队列模板#

单调队列最常见的模板其实就是下面这版：

Python3 点击展开代码

14 lines 展开代码

from collections import deque

q = deque()  # 存下标

for i, x in enumerate(nums):
    while q and nums[q[-1]] <= x:
        q.pop()
    q.append(i)

    if q[0] <= i - k:
        q.popleft()

    if i >= k - 1:
        ans.append(nums[q[0]])

如果同时需要维护最大值和最小值，就开两个队列：

一个单调递减，维护最大值
一个单调递增，维护最小值

而如果题目是 LC862 这种"前缀和 + 最短子数组"，那么队列里存的就不是原数组元素，而是前缀和下标。这一点要单独记。

优先队列：动态维护最值#

优先队列的核心思想#

优先队列的题，核心味道其实非常明显：

1
候选集会动态变化，但每一步只关心其中的一个最值。

这时就很容易想到堆。

常见信号包括：

一边扫描，一边动态加入候选
每次只需要当前最大 / 当前最小
Top K
多路归并
数据流维护第 k 大 / 中位数

在 Python 里，刷题时通常直接用 heapq：

默认是小根堆
想要大根堆，就存相反数

Top K 问题#

LC215 - 数组中的第 K 个最大元素#

Top K问题，可以通过快速选择算法来解决。我们这里先复习一下优化重复元素性能的三路快选。

Python3 点击展开代码

39 lines 展开代码

import random

def findKthLargest(self, nums: list[int], k: int) -> int:
    target = len(nums) - k

    def partition(left: int, right: int) -> tuple[int, int]:
        pivot_idx = random.randint(left, right)
        pivot = nums[pivot_idx]

        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]

        lt = left
        i = left
        gt = right

        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1

        return lt, gt

    left, right = 0, len(nums) - 1

    while left <= right:
        lt, gt = partition(left, right)

        if lt <= target <= gt:
            return nums[target]
        elif target < lt:
            right = lt - 1
        else:
            left = gt + 1

然后，我们就进入这一题的优先队列写法。一般优先队列题优先用heapq即可，堆就是优先队列的常见实现方式。我们通过取反模拟大根堆，然后弹出k-1个之后得到第k个最大元素。

Python3 点击展开代码

10 lines 展开代码

import heapq

def findKthLargest(self, nums: list[int], k: int) -> int:
    pq = [-x for x in nums]
    heapq.heapify(pq)

    for _ in range(k - 1):
        heapq.heappop(pq)

    return -heapq.heappop(pq)

另一种做法是固定大小的小根堆，这样会一直保留最小的k个，如果新元素比堆顶大，就换堆顶，到最后堆顶就会变成最大的k个中的最小的，也就是第k个最大元素。

Python3 点击展开代码

9 lines 展开代码

import heapq

def findKthLargest(self, nums: list[int], k: int) -> int:
    pq = []
    for num in nums:
        heapq.heappush(pq,num)
        if len(pq)>k:
            heapq.heappop(pq)
    return pq[0]

LC347 - 前 K 个高频元素#

这一题最符合直觉的做法是哈希表+小根堆，我们维持大小为k的小根堆，遇到大的就替换掉堆顶，最终就会剩余前k个高频元素。

Python3 点击展开代码

14 lines 展开代码

import heapq
from collections import Counter

def topKFrequent(self, nums: list[int], k: int) -> list[int]:
    freq_map = Counter(nums)
    pq = []
    for num, freq in freq_map.items():
        heapq.heappush(pq, (freq, num))
        if len(pq) > k:
            heapq.heappop(pq)
    
    # 此时只剩下了频率最高的K个元组
    ans = [x[1] for x in pq]
    return ans

LC703 - 数据流中的第 K 大元素#

Python3 点击展开代码

15 lines 展开代码

import heapq

class KthLargest:

    def __init__(self, k: int, nums: list[int]):
        self.pq = []
        self.k = k
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.pq,val)
        if len(self.pq)>self.k:
            heapq.heappop(self.pq)
        return self.pq[0]

合并多个有序结构#

LC23 - 合并 K 个升序链表#

之前合并k个升序链表是通过分治归并法解决，这里可以使用堆来解决这个问题。我们将所有链表当前节点放在最小堆里，每次取出堆顶构造。

Python3 点击展开代码

19 lines 展开代码

def mergeKLists(self, lists: list[ListNode]) -> ListNode:
    pq = []

    for i, head in enumerate(lists):
        if head:
            heapq.heappush(pq, (head.val, i, head))

    dummy = ListNode()
    p = dummy

    while pq:
        _, i, node = heapq.heappop(pq)
        p.next = node
        p = p.next

        if node.next:
            heapq.heappush(pq, (node.next.val, i, node.next))

    return dummy.next

需要注意的是，我们必须要防止 Python 直接比较 node，因为链表节点本身不能比较大小。所以我们要存 node.val 和 node 的元组。但是题目中 node.val 还是可能会相等，然后顺位又去比较 node，所以我们还要在中间塞一个 idx，来保证永远比不到 node。

LC373 - 查找和最小的 K 对数字#

最简单的写法就是二重循环全部入大小k的大根堆，每次超限踢出最大的，剩下的就是最小的K个。

Python3 点击展开代码

13 lines 展开代码

import heapq

def kSmallestPairs(self, nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
    pq = []

    for num1 in nums1:
        for num2 in nums2:
            total = num1 + num2
            heapq.heappush(pq, (-total, num1, num2))
            if len(pq) > k:
                heapq.heappop(pq)

    return [[a, b] for _, a, b in pq]

但是，这么写显然丢失了题目中的重要信息，即有序。假设nums1和nums2都有三个，我们可以写出3x3的矩阵，每一行都可以看成一个有序链表，比如1、7、11；2、4、6：

1
        2   4   6
2
1   ->  3   5   7
3
7   ->  9  11  13
4
11  -> 13  15  17

显然，我们就可以套用 LC23 的思路，先把每一行第一个数字入堆，然后弹出当前最小对，再继续看这一行的下一个，直到取满 k 个。

Python3 点击展开代码

20 lines 展开代码

import heapq

def kSmallestPairs(self, nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
    if not nums1 or not nums2 or k == 0:
        return []

    pq = []
    ans = []
    # 如果len(nums1)甚至不如k，那么后面的不用看了
    for i in range(min(k, len(nums1))):
        heapq.heappush(pq,(nums1[i]+nums2[0],i,0))

    while pq and len(ans)<k:
        _,i,j = heapq.heappop(pq)
        ans.append([nums1[i],nums2[j]])

        if j+1<len(nums2):
            heapq.heappush(pq,(nums1[i]+nums2[j+1],i,j+1))

    return ans

数据流与对顶堆#

LC295 - 数据流的中位数#

注意，没说输入的数据是按顺序的，虽然样例是按顺序的。这一题的解法是用两个堆，天然拿出左半边最大的和右半边做小的，注意做好奇偶处理。

Python3 点击展开代码

24 lines 展开代码

import heapq

class MedianFinder:

    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        # 偏小的最大堆：max_heap；偏大的最小堆：min_heap
        heapq.heappush(self.max_heap,-num)
        lower_biggest = -heapq.heappop(self.max_heap)
        heapq.heappush(self.min_heap,lower_biggest)
        # 要始终满足 len(max_heap) >= len(min_heap)最多只多 1 个
        # 关键点就在于来回倒腾的往往不是一个数，但是维持了数量关系
        if len(self.min_heap) > len(self.max_heap):
            upper_smallest = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap,-upper_smallest)


    def findMedian(self) -> float:
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        return (-self.max_heap[0]+self.min_heap[0]) / 2.0

贪心 + 优先队列#

有时候，我们需要一边扫描，一边动态加入候选，并且反复取当前最大/最小。

LC253 - 会议室 II#

堆维护"现在占着资源的人"

给一个安排时间的数组，每个会议时间包含开始和结束，返回所需会议室最小数量，也就是： [[0,30],[5,10],[15,20]] -> 2。

这一题，是通过最小堆+优先队列实现的，堆里的元素表示要占用到哪个时间点。这样，新元素如果大于最小堆的最早结束时间，说明可以重复使用这个会议室，我们移除堆顶然后入堆即可：

Python3 点击展开代码

16 lines 展开代码

import heapq

def minMeetingRooms(intervals): 
    if not intervals:
        return 0
    rooms = []
    intervals.sort(key = lambda x:x[0])
    heapq.heappush(rooms,intervals[0][1])

    for i in intervals[1:]:
        if i[0]>=rooms[0]:
            heapq.heappop(rooms)
        
        heapq.heappush(rooms,i[1])

    return len(rooms)

LC871 - 最低加油次数#

堆维护"过去留下来的备选资源"

这一题的标准思路是，我们维持一个大根堆，用fuel表示最远能到哪里，按顺序扫描所有加油站，把所有"已经能到达的站"的油量放入一个大根堆。如果当前的油不够去下一站/终点，就从大根堆里面拿一个最大的油补上，每弹一次堆，表示加油一次。

所以，这一题实际上是贪心用最大油量加，从而让加油量尽量少。为了实现这个贪心借助了堆结构。

Python3 点击展开代码

15 lines 展开代码

def minRefuelStops(self, target: int, startFuel: int, stations: list[list[int]]) -> int:
    pq = []
    fuel = startFuel
    i = 0
    n = len(stations)
    ans = 0
    while fuel < target:
        while i < n and stations[i][0] <= fuel:
            heapq.heappush(pq, -stations[i][1])
            i += 1
        if not pq:
            return -1
        fuel += -heapq.heappop(pq)
        ans += 1
    return ans

Python heapq 使用要点#

这里把 Python 里最常用的几个点单独记一下：

Python3 点击展开代码

8 lines 展开代码

import heapq

pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)
top = pq[0]              # 堆顶最小值
x = heapq.heappop(pq)    # 弹出最小值

几个高频注意点：

heapq 默认是小根堆
heapq.heapify(nums) 是原地建堆，返回值是 None
想模拟大根堆，通常存相反数
处理链表节点、对象、元组时，要注意比较规则
如果元组前几位可能相等，后面又是不可比较对象，需要补一个 idx

一句话记忆：

1
Python 里优先队列几乎就是 list + heapq。

栈与队列设计题#

栈的设计题#

LC155 - 最小栈#

核心是"普通栈存值 + 辅助栈同步最小值"。难点不在 API，而在于要不要让 min_stack 和主栈等长。本文前面用的是最稳妥的等长写法。

LC225 - 用队列实现栈#

核心是让队列模拟"最后进来的先出去"。最稳定的写法是双队列倒腾，把最后一个元素单独留下来当栈顶。

设计题的核心不是套模板，而是想清楚"我要额外维护什么信息"。

这两题分别对应：

LC155：普通栈 + 同步最小值栈
LC225：用两个队列模拟"最后进入的先出来"

队列的设计题#

LC232 - 用栈实现队列#

核心是让一个栈负责输入、另一个栈负责输出。只有在输出栈为空时，才把输入栈整体倒过去。

LC622 - 设计循环队列#

核心是循环数组 + 取模。建议统一采用"浪费一个位置"的写法，这样空和满的判断最清楚。

LC641 - 设计循环双端队列#

比 LC622 多的只是"两头都能操作"，本质仍然是循环数组和指针含义的统一。

队列设计题常见就三类：

普通队列：先进先出
循环队列：用取模节省空间
双端队列：两头都能插入和删除

这类题一定要先把指针含义定死，不然特别容易写着写着把自己绕晕。最推荐的定义方式是：

front 指向队头元素
rear 指向队尾后一个空位
空队列：front == rear
满队列：浪费一个位置，判断 (rear + 1) % capacity == front

栈与队列题目的分类判断#

一看到括号匹配、消消乐、撤销操作，就想栈#

因为这类题都在维护"最近一个还没处理完的状态"。括号要和最近的左括号配对，消消乐要和最近的字符比，撤销也总是撤销最近一步。

一看到层序遍历、按顺序处理、最短步数，就想队列#

因为队列天然按顺序推进，而 BFS 又天然按层扩散。凡是"从起点最少几步到终点""一轮一轮蔓延"的题目，优先就该想到队列。

一看到下一个更大元素、找左右边界，就想单调栈#

这类题本质都在找"第一个打破单调性的位置"。只要当前元素一来，前面一批元素的答案就能被结算，这就是单调栈最典型的信号。

一看到滑动窗口最大值、窗口最小值，就想单调队列#

因为窗口在移动，而我们又需要实时拿到窗口最值。暴力 max/min 会超时，于是就要用单调队列维护窗口内部的有效候选。

一看到动态最值、Top K、多路归并，就想优先队列#

堆的关键词不是"排序"，而是"动态维护"。候选集一直在变，但每一步只要其中一个最值，这时优先队列就很自然。

栈与队列常见模板#

普通栈模板#

Python3 点击展开代码

7 lines 展开代码

stack = []

for x in nums:
    stack.append(x)

while stack:
    x = stack.pop()

普通队列模板#

Python3 点击展开代码

8 lines 展开代码

from collections import deque

q = deque([start])

while q:
    cur = q.popleft()
    for nxt in neighbors(cur):
        q.append(nxt)

双端队列模板#

Python3 点击展开代码

7 lines 展开代码

from collections import deque

dq = deque()
dq.append(x)
dq.appendleft(y)
dq.pop()
dq.popleft()

括号匹配模板#

Python3 点击展开代码

11 lines 展开代码

pairs = {')': '(', ']': '[', '}': '{'}
stack = []

for ch in s:
    if ch not in pairs:
        stack.append(ch)
    else:
        if not stack or stack.pop() != pairs[ch]:
            return False

return not stack

单调栈模板#

Python3 点击展开代码

7 lines 展开代码

stack = []

for i, x in enumerate(nums):
    while stack and nums[stack[-1]] < x:
        idx = stack.pop()
        # 结算 idx
    stack.append(i)

单调队列模板#

Python3 点击展开代码

11 lines 展开代码

from collections import deque

q = deque()

for i, x in enumerate(nums):
    while q and nums[q[-1]] <= x:
        q.pop()
    q.append(i)

    if q[0] <= i - k:
        q.popleft()

优先队列模板#

Python3 点击展开代码

9 lines 展开代码

import heapq

pq = []

for x in nums:
    heapq.heappush(pq, x)

while pq:
    x = heapq.heappop(pq)

栈与队列问题总结#

这一篇内容看起来很多，但其实核心只有几句话：

栈解决最近、嵌套、回退
队列解决顺序推进、层序扩散、最短步数
单调栈解决"第一个更大/更小"和边界
单调队列解决滑动窗口最值
优先队列解决动态候选集里的最值问题

如果要把整篇再压缩成一句话，那就是：

1
不要先背题，而是先判断题目需要维护哪一种顺序。

当你开始能从"维护顺序"的角度看题时，栈、队列、单调栈、单调队列、优先队列这几个专题就会越来越像一家人，而不是零散的很多模板。