栈刷题实战：从括号匹配到单调栈的延迟结算思维

早上九点，我在电脑前坐下来，把这一天的任务定成了 Hot100 里的栈题。速通计划走到第七天，节奏已经比较稳：数组、哈希、双指针、滑动窗口、子串，每天都按主题往前赶。栈原本是我以为最轻松的一类，毕竟括号匹配这种题大学写了无数遍，全专题最多也就打卡二十分钟——真正坐在题目面前才发现，这个想法错得离谱。Hot100 里栈相关的题有十几道，真正卡住我的不是那些花哨的字符串题，而是单调栈和直方图那道 Hard 题背后共用的那套“延迟结算”思维。

我把今天的实战路线整理一遍，准备写给两类人：一类是跟着 Hot100 刷题、第一次系统碰栈的朋友，另一类是刷完一遍但总觉得栈题变化太多、想找个统一规律收拢思路的人。今天的体会浓缩成一句话：栈题吃的是模型，不是手速。括号、路径、表达式、单调栈、双端队列，说到底都是同一套状态账本的变体。

1. 先把可秒的栈题清掉：括号、路径、表达式里藏着同一套状态逻辑

Hot100 栈专题里，真正属于“基础栈”的题大概是这些：有效的括号、简化路径、逆波兰表达式求值、最小栈、用栈实现队列。这几道题我一开始没给自己时间压力，目的很明确——把栈的基本操作刷到形成肌肉记忆，因为后面几道 Hard 题的底子全在这里。

这几道题有个共同点：都给了你一个从左到右扫描的序列，而某个位置的配对信息注定要等到后面才知道。括号要等到右括号出现才能确认匹配，路径段要等到 .. 出现才能决定要不要删，表达式要等到运算符出现才能把操作数拿出来算。这种“未来才能结算”的事，就是栈存在的理由。

1.1 括号匹配：闭合时反向找最近配对

有效的括号几乎是我最开始学的算法题之一，但今天重写还是有点新体会。最核心的点在于：遇到左括号时不能立刻处理，必须先压进栈；遇到右括号时，从栈顶弹出那个“最近的未匹配左括号”，看是不是和自己配对。如果栈本身是空的，或者栈顶不对，就直接判失败。

python复制def isValid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

为什么这道题不能用计数器解决？很多人第一反应是分别数三种括号的数量，最后看左右是否相等。但嵌套结构 ([)] 这种输入，左右括号数量都是两两相等，却不是有效括号。括号的有效性不只看数量，还看层级，栈天然能保存“当前处在哪一层”的信息。这个领悟很小，但是后面所有栈题的基础。

1.2 简化路径和逆波兰表达式：把上下文压栈，遇到回溯操作再弹

简化路径这道题，题目看着是字符串处理，实质上就是模拟文件目录的层级。我用 Python 的 split('/') 把路径拆开，然后逐个处理段落：空字符串和 . 直接跳过，.. 就弹出栈顶，普通路径段压进栈。最后只要把栈里的目录重新拼一个 / 开头出来就行。

python复制def simplifyPath(path: str) -> str:
    stack = []
    for part in path.split('/'):
        if part == '..':
            if stack:
                stack.pop()
        elif part and part != '.':
            stack.append(part)
    return '/' + '/'.join(stack)

这道题的经验是：路径本身就是一个层级栈，.. 相当于“回到上一级”，所以遇到它必须弹栈。唯一要注意的是不能在空栈的时候弹，否则会越界。很多新手在这里写错，就是因为没想明白“栈空代表已经回到根目录”这件事。

逆波兰表达式稍微绕一点，因为栈里存的是操作数。遇到数字直接压栈，遇到运算符就从栈里弹出两个数来计算。这里有个坑我刚开始也踩过：弹出的两个数，先弹出来的是右操作数，后弹出来的是左操作数。做减法和除法的时候顺序反了，结果就是错的。

python复制def evalRPN(tokens: List[str]) -> int:
    stack = []
    ops = {'+', '-', '*', '/'}
    for token in tokens:
        if token in ops:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    return stack[0]

判断运算符这里我坚持用集合判断，而不是 isdigit()。因为负数 -11 会被误判成不是数字，进而走错误分支。这个细节比较刁钻，但是真实面试里很容易被问到。

1.3 设计题：最小栈与用栈实现队列，状态管理才是重点

最小栈要求 getMin() 是常数时间，所以光靠一个栈不够。我的做法是维护两个栈：数据栈照常存输入，辅助栈每次存“当前发生过的最小值”。也就是说，每次 push 的时候，辅助栈压入的是 min(当前值, 辅助栈栈顶)，这样查询最小值永远只看辅助栈栈顶就行。

python复制class MinStack:
    def __init__(self):
        self.data = []
        self.mins = []
    def push(self, val: int) -> None:
        self.data.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)
    def pop(self) -> None:
        if self.data.pop() == self.mins[-1]:
            self.mins.pop()
    def top(self) -> int:
        return self.data[-1]
    def getMin(self) -> int:
        return self.mins[-1]

我刚才写的这个版本是“不同步弹出”的写法：只有当数据栈弹出的是最小值时，辅助栈才跟着弹出。它的好处是辅助栈空间不一定和数据栈一样大，坏处是 pop 的时候要做一次比较判断。也有另一种写法是每次数据栈 pop 时辅助栈无条件 pop，因为辅助栈其实记录的是“每个时刻的最小值历史快照”。两种都正确，我更推荐后者，因为代码更对称，出错概率更低。

用栈实现队列也是一道经典设计题：双栈翻转。入队直接往 inStack 里压，出队先看 outStack 是不是空，如果空了就把 inStack 全部倒进 outStack，再弹出 outStack 的栈顶。

python复制class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []
    def push(self, x: int) -> None:
        self.in_stack.append(x)
    def pop(self) -> int:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

为什么不在每次入队时都倒一遍？因为只有出队的时候才需要保证顺序，平时不用倒。这种“能拖就拖”的懒操作，摊还下来每个操作都是 O(1)。这其实就是后面单调栈里“延迟结算”思想的雏形——先把该做的计算攒着，等到真需要结果的那一瞬间一起处理。

2. 单调栈不是暴力：延迟结算才是它全部的脑子

今天真正让我开窍的部分从每日温度开始。这道题输入是一个温度数组，要求返回每个位置后面第一个比它高的温度过了几天。最直观的方法是双重循环，每个位置向后找第一个更大值，复杂度 O(n²)。但栈专题的意义，就是教你把这种“向后找”的查询全部用单调栈在线性时间里做完。

2.1 每日温度：先学会“不急着算”的代码节奏

单调栈的思路特别反直觉，它不是在遇到一个数的时候立刻去找后面的答案，而是反过来：当你遍历到右边某个值的时候，回头看栈里哪些数可以被这个值“结算”。

python复制def dailyTemperatures(temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    ans = [0] * n
    stack = []
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            prev = stack.pop()
            ans[prev] = i - prev
        stack.append(i)
    return ans

我第一遍看这个模板时完全懵了，为什么弹出栈顶的时机是“当前温度比栈顶高”，而不是“当前温度比栈顶低”？后来想明白了：栈里保存的是那些“已经出现、但还没找到右侧更高温度”的位置，而且这些位置的温度从栈底到栈顶是递减的。当一个新的高温度出现时，栈里所有比它低的旧温度都可以立刻结算，因为它们等到了结果。之后这个新温度自己也压进栈里去等它的未来。

这个过程就像排队时有人个子特别高，于是所有比他矮的旧人瞬间被点亮了答案。核心是不急着为每个元素找未来，而是维护一个“尚未被解决”的矮个子序列。

2.2 下一个更大元素：单调栈跑一遍，用哈希表顺手存答案

每日温度做完，下一题其实是同一套模板换壳。下一个更大元素第一题给了一个长数组 nums2，要求的是另一个短数组 nums1 里每个元素在 nums2 中的下一个更大元素。做法很直接：先用单调栈遍历一遍 nums2，把每个元素的“下一个更大元素”记录到字典里，最后查字典就行。

python复制def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    nxt = {}
    stack = []
    for x in nums2:
        while stack and stack[-1] < x:
            nxt[stack.pop()] = x
        stack.append(x)
    for rest in stack:
        nxt[rest] = -1
    return [nxt[x] for x in nums1]

这个解法里唯一的新增点是：字典的值是元素本身而不是索引，因为题目让我们返回的是大小关系而不是距离。单调栈模板变化时可以以“结算结果要存什么”为依据来决定索引还是值的取舍。每日温度需要算天数，所以存索引；下一个更大元素需要返回具体值，所以直接存 x。很多题目所谓的“变体”，本质上就是这里换了需求。

2.3 柱状图中最大的矩形：哨兵是正确性的一半

柱状图中最大的矩形是今天最让我抓狂的一道 Hard。题意不复杂：给定一个高度数组，找最大的矩形面积。暴力做法是以每个柱子为中心，向左右扩到比它矮的边界，然后算面积，复杂度 O(n²)。再进一步是单调栈，用延迟结算的方式对每个高度算它能覆盖的宽度。

正确的单调栈模板是这样的：

python复制def largestRectangleArea(heights: List[int]) -> int:
    # 左右各加一个高度为 0 的哨兵
    heights = [0] + heights + [0]
    stack = [0]
    ans = 0
    for i in range(1, len(heights)):
        while heights[stack[-1]] > heights[i]:
            idx = stack.pop()
            ans = max(ans, heights[idx] * (i - stack[-1] - 1))
        stack.append(i)
    return ans

先解释一下为什么要加哨兵。单调栈里结算的触发条件是“新柱子高度小于栈顶”。遍历结束后，如果不加右边的哨兵 0，栈里可能还存着一些一直在上升的柱子，它们的面积还没被计算过，这就需要额外的收尾循环。加入高度为 0 的哨兵后，它一定会比栈里所有剩余元素矮，所以那个 while 循环会把这堆存量全部结算掉。左侧的哨兵 0 同样重要，它保证栈永远不会为空——这样每当弹出栈顶后，stack[-1] 还能取到合法的左边界，不用额外写 if stack 判断。

这里有一个细节我曾经写错过：弹出栈顶元素后，宽度为什么是 i - stack[-1] - 1，而不是 i - idx 之类的算式？因为当前弹出元素的高度是 h，它能形成矩形的范围，是从它左边的第一个更矮柱子之后，到它右边第一个更矮的柱子之前。在单调栈里，弹出它时，它右边第一个更矮的柱子就是当前遍历到的 i，它左边第一个更矮的柱子就是新的栈顶。所以宽度就是右边界索引减去左边界索引再减一。这个边界关系一旦理解清楚，代码就不会再手抖写错。

关于相等高度，我再补一点经验：我的模板用严格大于 > 作为弹出条件，相等时不弹出。这样做的理由是，相同高度的柱子之间不应该提前把高度结算掉，让后面的柱子再去扩展同一高度的矩形，才能覆盖更大的底边宽度。如果你用 >=，有些相同高度的区间会漏算，虽然结果在某些数据上也能对，但边界案例容易翻车。从易理解的角度，严格大于最保险。

3. 最长有效括号：栈解法把索引当成账本，DP 是另一条路

今天栈题里唯一让我停下来重新推了两遍的是最长有效括号。题目给一个字符串，要求找最长的一段连续有效括号子串。这一题我之前看过题解，也刷过一次，但今天重新写的时候还是很乱。

3.1 为什么直观的“匹配计数法”总是错

很多人会先想到用栈去括号，每次遇到右括号就把左括号弹出，然后数一下已经弹出的数量。这个思路看起来合理，但实际上没法处理括号之间的连续性。比如 ()(()) 这种，栈弹出的总数量是 3 个左括号，但最长有效子串长度是 6 而不是 3。我们必须把“当前这组合法括号段的起点”也记录下来，才能算出连续长度。

另一个常见直觉是“记录子串起点”，遇到不匹配的右括号就把起点重置到右括号后面一位。这个思路方向是对的，但在嵌套的括号里，起点更新时机容易算错。最稳妥的写法是：栈底永远保存“最后一个没有被匹配的右括号的索引”。

3.2 正确栈解法：把最后一个未匹配右括号当锚点

python复制def longestValidParentheses(s: str) -> int:
    stack = [-1]
    ans = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                ans = max(ans, i - stack[-1])
    return ans

为什么要先往栈里塞一个 -1？这个 -1 是虚拟的“未匹配右括号”，它会一直留在栈底，直到被某个多余的右括号替换。具体流程是：遇到左括号，把它的索引压栈；遇到右括号，先弹出一个左括号索引，如果栈不空，就用 i - stack[-1] 更新答案。这里 stack[-1] 永远是当前这一串连续有效括号段“起点前一格”的位置。

如果栈空了，说明这个右括号把右侧的左括号全部匹配完了，那它本身就成了一个新的“未匹配右括号”，所以要把它自己也压进栈，作为下一段的起点锚点。这个细节非常关键，没有锚点的版本就像记账时没有余额结账，永远算不对一串连续的括号。

我一开始把 stack.pop() 用了两次，遇到右括号就弹栈然后立刻取新的 stack[-1]，结果在 "(()" 这个用例上算出了错误答案。后来自己想明白：对一个右括号来说，第一步应该是把当前能配对的那个左括号索引弹出去，然后剩下的栈顶才是我们想找的“段落左边界”。如果弹完栈空了，那段落不得不从头开始，不能继续累加。

3.3 DP 对照：帮你看清 O(n) 里的隐藏状态

这一题也可以用动态规划做，逻辑完全等价但思考角度不同。dp[i] 表示以第 i 个字符结尾的最长有效括号长度。如果 s[i] == '('，那 dp[i] = 0；如果是 ')'，就要看它左边是什么：

• 如果 s[i-1] == '('，那么刚好和当前右括号配对，dp[i] = dp[i-2] + 2。
• 如果 s[i-1] == ')'，则需要找 i - dp[i-1] - 1 位置是不是左括号。如果是，说明当前这一对括号可以把它内部的 dp[i-1] 以及更早的 dp[i - dp[i-1] - 2] 串起来。

这个转移方程确实能写对，但我个人在比赛状态里更愿意用栈解法，因为不用记忆复杂的下标关系。栈解法里的“栈底锚点”加上“索引差”，本质上就是 DP 里那个隐藏状态的直观版本。两种方式我都建议至少写一遍，才能理解为什么右括号栈空时要把当前索引压回去。

4. 滑动窗口最大值：题放在栈分类里，解法却是个会过期的单调栈

滑动窗口最大值这题在 Hot100 里常被归到栈/队列专题，当初刷的时候我一度认为分类出了问题。这题要求每次窗口滑动时返回窗口内最大值，暴力做法是每次遍历窗口求最大，复杂度 O(n·k)。合理解法是用双端队列，时间 O(n)。

4.1 双端队列与单调栈：同一个延迟结算模型

我把双端队列解法称为“会过期的单调栈”，因为它的核心思路和单调栈完全一样：维护一个从头到尾降序的候选序列，新的值从尾部进入时，把所有比它小的旧值全部弹出，因为它们以后永远不可能成为窗口最大值。

python复制from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    q = deque()
    ans = []
    for i, x in enumerate(nums):
        # 移出窗口范围的下标
        if q and q[0] <= i - k:
            q.popleft()
        # 新的 x 会挡住所有年龄更大的较小值
        while q and nums[q[-1]] <= x:
            q.pop()
        q.append(i)
        # 窗口完整后才开始记录答案
        if i >= k - 1:
            ans.append(nums[q[0]])
    return ans

单调性体现在队列从队首到队尾是递减的。队首就是当前窗口的最大值候选者。这里和单调栈不同之处在于：栈只有尾部进出，而队列需要从头部移除过期索引。这就是为什么题目不叫单调栈而是双端队列。但它们共用的模型是一样的——把暂时不能结算的元素攒在容器里，等到合适的时机再处理。

4.2 三个最容易写错的细节：过期、相等和窗口未成型

我写这题的时候犯了三个错误，都挺典型。

第一个是过期判断。第一个版本我写成了 if q and q[0] < i - k，应该用 <=。窗口是左闭右开还是闭区间？当 i 是当前右边界时，左边界是 i - k + 1，所以凡是 <= i - k 的下标都已经离开窗口范围了。用小于号会漏掉恰好等于边界的元素，导致队列里混进已经不在窗口中的旧最大值。

第二个是相等元素的处理。我用的是 <= 弹出，也就是当新元素和队尾元素相等时，把旧元素弹出去。为什么要这样？因为旧元素更早过期，新元素能活得更久，保留新元素是更优选择。如果你用严格小于弹出，相等元素会滞留在队列里，可能成为虚假的最大值来源，处理起来很麻烦。

第三个是窗口未成型时取答案。最早的版本我在循环体里每当 i >= k 甚至更早的时候就去取队首，然后发现开头几个窗口答案不对。正确的做法是先不断把元素塞进队列，直到窗口完整，也就是 i >= k - 1 之后才收集结果。这个判断虽然简单，但是顺序错了整个答案都会错。

4.3 手推一遍 k=3 的过程

拿 nums = [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小为 3。

• i=0，队列空，入队 0，队列是 [0]。
• i=1，3 > 1，所以 0 被弹出，入队 1，队列是 [1]。
• i=2，-1 < 3，直接入队 2，队列是 [1, 2]，此时 i >= 2，取 nums[1] = 3。
• i=3，队首 1 还在窗口内，-3 入队，队列是 [1, 2, 3]，最大值 3。
• i=4，队首 1 已经离开窗口，弹出；5 > -3，先弹 3，再弹 2，队列变成 [4]，最大值 5。
• 后面以此类推。

这个手推过程帮我真正理解了为什么队列里维护的是“候选者”而不是“所有元素”。那些被弹出的小值，从弹出的那一刻起就注定当不了窗口最大值了，留在容器里只会浪费计算。

5. 复盘一下今天的坑和明天的安排：栈题吃的是模型，不是手速

今天刷完一轮，我把错误集中整理一下。栈题的坑大多数不在“栈”本身，在过去没过也常犯的细节。我把它们列成一张表，给自己做错题本，也给读者一个避坑清单。

今天踩到的坑：

这几个坑里最值得警惕的是索引和值的互换。栈题里什么时候存值、什么时候存索引，完全取决于你要结算的是“差值大小”还是“值的大小”。每日温度要的是天数差，所以存索引；下一个更大元素要的是答案本身，所以存值。很多题解看起来像是变魔术，其实就是抓了这个核心差异。

再说说明天的事。速通计划到了第 8 天，这个阶段最适合做的事，是把栈、单调栈和双端队列放一起交叉复习。因为它们本质上是在说同一件事：用一个持有状态的容器，把暂时算不出来的结果延后，等右边元素来了以后统一结算。单调栈是只在尾部操作的延迟结算，双端队列是头部还要加一个过期机制的延迟结算，最小栈和辅助栈则是把历史状态分层保存。

我的一个小习惯是：思维模型统一后，关闭题目页面，把单调栈模板和滑动窗口模板各默写一遍。如果第二天还能在五分钟之内把它们完整写出来，这组题才真的算是吃进去了。

其实今天最大的收获不是某一道题的解法，而是我终于接受了“栈不是一个用来存储的容器，而是一个用来管理时间的容器”这个说法。每一次入栈都是在说“我现在不敢下结论”，每一次出栈都是在说“现在可以结算了”。明白这个，Hot100 里的栈题就已经被看穿了一大半。