栈的经典应用：括号匹配与区间合法性判断的全流程解析

前几天重新翻洛谷题单，又把 P8430 翻出来了。这题的标识很直白：【栈】P8430 [COI 2020] Zagrade，难度普及+。Zagrade 在克罗地亚语里就是“括号”，COI 2020 的题目，名字一出来，基本等于告诉选手：这题要处理括号匹配，而括号匹配背后几乎必然站着栈这个数据结构。你要是觉得“括号匹配不是用计数器就行吗”，那这道题恰恰能把你这个认知掰开揉碎。

如果你正在备赛 CSP-J/S，或者刚学完栈想找题练手，我认为这题是很好的试金石。它不考高级算法，却会把“栈到底在解决什么问题”揉进括号结构里。你能独立写出完整思路，说明对栈已经有第一层理解；如果已经能秒掉“判断整个串是否合法”，那文章后面谈到的区间判断和括号类变种，仍值得你多停留几秒。

1. 先想明白：为什么括号配对天生就要用栈

1.1 合法括号序列的递归定义，和栈是同构的

平时我们说一个括号串合不合法，脑子里其实有一个隐藏的递归定义：

• 空串是合法括号序列；
• 如果 A 是合法括号序列，那么(A)也是合法括号序列；
• 如果 A 和 B 都是合法括号序列，那么 AB 也是合法括号序列。

这个定义熟悉吧？你去看(()())()，它先是一个大括号包着()()，后面又并列一个()。这种“嵌套 + 并列”结构，天然对应一种处理顺序：最晚遇到的左括号，要最先被匹配掉。

这种“后到先处理”的顺序，恰好就是栈的 LIFO（后进先出）。所以大家常说括号匹配是栈的经典应用，不是因为题目故意为难你，而是括号语言的结构本身就是一个栈结构。你问一个正在写编辑器的程序员，为什么光标放在右括号上编辑器能帮你高亮对应的左括号？底层逻辑也很简单：扫描一遍文本，把没见过右括号的左括号位置往栈里压，见到右括号就弹栈顶，弹出来的就是匹配位置。

如果不太理解嵌套关系，可以想象一摞盘子：你往桌上叠了三个盘子，要拿也只能先拿最上面那个。括号嵌套时，((()))最外层的左括号，反而是最后才被右括号匹配掉的，这和栈顶弹出完全一致。

1.2 为什么只统计左右括号数量一定不够

很多初学者第一反应是：我开一个变量 cnt，遇到(加 1，遇到)减 1，最后 cnt 等于 0 不就行了？

对一部分括号题，这个方案确实够用。比如只问“整个串是否合法”，一个计数器就能做。但麻烦在于计数器记不住“谁和谁配对”。反例也很常见：

())(

数一数左右括号数量，两个左括号两个右括号，总数相等，计数器最终归零。可是你看这个串，第三个字符是)，它出现时前面只剩下一个已经匹配完的左括号，根本轮不到它去配对，所以它是个多余右括号，整个串不合规。

只统计数量的问题就在这里：计数器只知道“最终有没有多余的括号”，但不知道“是不是每个右括号都排在了可配对的左括号后面”。括号顺序一旦乱了，数量照样对，结构已经坏了。这时候你得有一个结构，能记住“当前哪些左括号还没被匹配”，并且每次只取最近一个未匹配的左括号来配对——这不就是栈吗。

1.3 从字符栈到下标栈：真正重要的是位置

很多人做括号题，第一版代码会写成这样：

stack<char> st; for (char c : s) { if (c == '(') st.push(c); else { if (st.empty()) return false; st.pop(); } }

这种写法能判断整体是否合法，但没法回答很多后续问题：这个右括号匹配的是哪个左括号？这两个括号之间的区间长度是多少？子串[l,r]是否合法？

想要回答这些问题，栈里就不能只存字符(，而要存这个左括号在原串里的下标。下标就是括号的身份证号，有了它，你才能记录完整的配对关系。

举个例子，考虑串(()())()，我们用数组栈模拟一下过程。stk里存的是左括号下标：

i=1 char=( stk=[1] i=2 char=( stk=[1,2] i=3 char=) 匹配到下标2，记录 match[2]=3, match[3]=2，弹出后 stk=[1] i=4 char=( stk=[1,4] i=5 char=) 匹配到下标4，记录 match[4]=5, match[5]=4，弹出后 stk=[1] i=6 char=) 匹配到下标1，记录 match[1]=6, match[6]=1，弹出后 stk=[] i=7 char=( stk=[7] i=8 char=) 匹配到下标7，记录 match[7]=8, match[8]=7，弹出后 stk=[]

这个例子展示了两件最关键的事：嵌套括号是靠“栈顶就是这个左括号最近的未匹配者”完成的；并列括号通过栈弹空后重新压栈完成。每一对括号的匹配关系都记录在match数组里，后面所有问题都能围绕这张配对表展开。

2. 核心解法拆解：配对完成后，剩下的问题往往需要“换个视角”

2.1 单串合法判断：一遍扫描解决三种情况

如果你只需要判断整个串是否合法，核心逻辑其实可以收敛得很干净，无非三种情况。

bool checkWholeString(const string& s) { int bal = 0; for (char c : s) { if (c == '(') { bal++; } else { bal--; if (bal < 0) return false; // 右括号比左括号先出现且无多余左括号可对应 } } return bal == 0; }

这个写法比字符栈更省，因为它只记录了“左括号剩余数量”，不需要关心具体哪个位置。但请注意，它无法回答“某个右括号匹配了哪个左括号”这个问题。所以做题时我习惯先问自己一句：题目要不要用到括号之间的具体配对关系？如果要用到，老老实实开栈存下标比单纯计数器稳妥得多。

有的题目甚至不需要保证整个串合法，比如求最长的合法括号子串，这时候中途出现多余右括号不能直接 return false，你只需要刷新起点并继续扫描。这就是为什么不能背一套模板打天下的原因：你得知道每段代码到底守住了什么条件，后续有变种时才能现场改。

2.2 区间合法性判断：前缀和把一个区间问题变成两个条件

假设题目从“判断整个串”升级成“回答 m 次询问，每个询问给一个区间 [l,r]，问这个子串是否合法”，此时每次重新用栈扫一遍区间会超时，需要更快的方式。

括号序列有一个非常巧妙的数值化方法：把(看成 +1，把)看成 -1，记前缀和数组pre[i]表示前 i 个字符的总和。于是对于一个区间 [l,r]，合法性可以被压缩成两个数值条件：

第一，pre[r] - pre[l-1]必须等于 0。这个条件保证了左右括号数量相等，因为总和抵消了。 第二，区间 [l,r] 内任意位置的前缀和都不能掉到pre[l-1]以下。也就是说：

min(pre[l], pre[l+1], ..., pre[r]) >= pre[l-1]

第二个条件很关键，它抓住了“顺序错误”的问题。看串)()，左括号和右括号数量相等，但第一个字符就是右括号，扫描到第一个位置时pre已经比pre[l-1]低了，所以它不可能合法。用数学语言说，合法括号序列的另一个等价定义是：任意前缀中左括号数量不少于右括号数量，且最终左右总数相等。区间 [l,r] 合法，就是在区间内部满足“任意前缀左括号不小于右括号”，这正好等价于pre的最小值不能低于区间左侧的起始值。

统计区间最小值的经典工具很多，因为这里只做查询、没有修改，用 ST 表最稳，O(1) 回答每个询问。也可以用线段树，但属于杀鸡用牛刀，因为预处理一次后所有查询都是静态的。

我个人很喜欢这种分拆：栈先负责“谁匹配谁”的结构关系，前缀和再负责“区间是否合法”的数值判断。两者解决的问题不同，却经常在同一道题里出现。如果你只懂得其中一个工具，碰到复合题就会卡住。

2.3 复杂度测算：为什么 O(n log n) 是可接受的

如果数据范围是 n ≤ 2e5，m ≤ 2e5，那么：

• 括号配对预处理是 O(n)，一遍扫描；
• 前缀和预处理是 O(n)；
• ST 表预处理是 O(n log n)；
• 每个区间询问通过 ST 表 O(1) 回答，总复杂度 O(n log n + m)。

对比每次询问临时扫区间 O(mn)，差距非常明显。n=2e5 时 O(n log n) 完全可以接受；而 O(mn) 在最坏情况下是 4e10 级别，肯定超时。所以这种题真正的难点不是实现多花哨，而是能不能想到把括号串数值化，再用 RMQ 去维护。

3. 代码落地：手写数组栈 + ST 表实现全流程

3.1 完整参考代码（C++17）

下面这份代码是我平时练习的风格：全部用数组模拟，不依赖 STL 的 stack，便于在需要访问栈内元素时直接操作。

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; const int MAXLOG = 20; int n, m, top; char s[MAXN]; int stk[MAXN]; // 手写栈，存左括号下标 int match[MAXN]; // match[i] 表示 i 的配对下标，若没有配则为 0 int pre[MAXN]; // 前缀和：( 为 1，) 为 -1 int lg[MAXN]; int st[MAXLOG][MAXN]; // ST 表维护区间前缀和最小值 int queryMin(int l, int r) { if (l > r) return INT_MAX; int k = lg[r - l + 1]; return min(st[k][l], st[k][r - (1 << k) + 1]); } bool isLegal(int l, int r) { if (pre[r] - pre[l - 1] != 0) return false; // 左右括号数量不同 if (queryMin(l, r) < pre[l - 1]) return false; // 区间内出现非法前缀 return true; } int main() { scanf("%s", s + 1); n = strlen(s + 1); // 第一次扫描：用栈记录括号配对关系 for (int i = 1; i <= n; i++) { if (s[i] == '(') { stk[++top] = i; } else { if (top > 0) { match[i] = stk[top]; match[stk[top]] = i; top--; } else { match[i] = 0; // 多余的右括号，没有可匹配的左括号 } } } // 计算前缀和 for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1] + (s[i] == '(' ? 1 : -1); } // 预处理 lg，用于 ST 表查询 lg[1] = 0; for (int i = 2; i <= n; i++) { lg[i] = lg[i >> 1] + 1; } // 构建 ST 表 for (int i = 1; i <= n; i++) { st[0][i] = pre[i]; } for (int j = 1; (1 << j) <= n; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]); } } // 假设接下来的输入是若干组区间询问 scanf("%d", &m); while (m--) { int l, r; scanf("%d%d", &l, &r); puts(isLegal(l, r) ? "YES" : "NO"); } return 0; }

有几个细节我特意按自己的习惯处理，简单说明一下。

字符数组从下标 1 开始存，避免后面处理前缀和时反复纠结 0 和 1 的偏移。pre[0] = 0在 C++ 全局变量里会自动初始化，所以前面不需要手动赋值。match数组初始为 0，表示很多下标可能没有匹配对象，查询前要先想清楚这一点，不要假设每个括号都能匹配。

3.2 手写栈为什么比 STL stack 更好用

很多教学代码用std::stack<int>，这对出题人来说完全没问题。但我自己写括号类题目时更常手写栈，有三个现实原因：

第一，手写栈可以随意访问栈内任意元素。比如某些变种题需要看“当前栈底元素是谁”，用std::stack做不方便，顶多能看栈顶；用数组栈，直接读stk[1]就行。第二，手写栈在调试时更容易打印全貌。你可以写个for循环，把栈里所有下标打出来看，这对理解嵌套过程帮助极大。第三，性能几乎没差别，但手写代码少了一层封装，在部分老 OJ 上能省下一点常数，习惯了就会觉得更清爽。

如果你刚开始练，我也建议先在草稿纸上手动模拟一两组数据，再对着代码看。

3.3 每个关键 if 到底守住了什么

写这道题容易犯迷糊的地方，往往不是算法本身，而是小逻辑。

pre[r] - pre[l - 1] != 0这个判断是为了防止左右括号数量不一致。queryMin(l, r) < pre[l - 1]是为了防止区间内部某个前缀已经出现右括号过剩。很多人会误写成queryMin(l, r) < 0，这在 l 恰好为 1 时没差别，但一旦 l 不是 1，前缀和的基准就不再是 0 了。这里的边界非常容易错，建议在代码旁边写清楚：我们比较的是“相对于区间开头的偏移量”，而不是绝对前缀和。

match数组本身这道题里不一定直接使用，但它能帮你理解整串结构。比如判断 [l,r] 是否合法时，如果match[r] == l且中间部分也合法，那至少说明外层是成对的。不过只要前缀和的条件满足，这类判断其实已经包含进去了，不需要额外借助 match。写完代码后你可以多造几个样例，把 match 数组打印出来对照看，对理解帮助很大。

4. 常见 WA 与排查实录：我在这类题上翻过的车

4.1 最容易写错的五个细节

我在带新生训练时发现，这道题最常出问题的地方往往是看起来无关紧要的小细节。整理成一张表：

第一类错误是最典型的。如果你用bal < 0的计数器法，遇到())(时第三个字符会让bal变成 -1，所以其实可以被拦下；但如果你只判断最终bal == 0，那就坏了。很多人在竞赛环境里手一抖就会只写最终判断，样例又能过，结果交上去全 WA。

4.2 一个非常隐蔽的区间判断坑

假设查询区间是[l, r]，你算出来pre[r] - pre[l-1] == 0，但区间内部的pre最小值恰好等于pre[l-1]，这时候区间合法吗？答案是合法。

比如串()，前缀和为 [1, 0]，如果查整个区间，从 1 到 2，查询区间内最小值是 0，pre[l-1] = pre[0] = 0，相等，满足条件，合法。如果题目允许区间左端点不是 1，条件也依然是一样的：只要最小值没有低于区间左侧基准，就不会出现非法前缀。

我自己的低级错误是以为“最小值大于 0”才对，忽略了这个 0 是相对于哪个位置的 0。测试一个l=2, r=4的样例就能暴露问题。这里建议在代码里把整个前缀和数组打印一遍，配合查询手动验证一次，比凭空推理快得多。

4.3 调试建议：写一个暴力程序对拍

区间合法判断这种题，特别适合对拍。暴力思路很简单，每次询问从 l 到 r 重新跑一遍栈统计即可：

bool brute(int l, int r, const string& s) { int cnt = 0; for (int i = l; i <= r; i++) { if (s[i] == '(') cnt++; else { cnt--; if (cnt < 0) return false; } } return cnt == 0; }

随机生成短括号串，用小范围 n, m 把暴力结果和 ST 表查询结果对比，不一致时打印区间和具体字符。这个方法能在一分钟内帮你发现边界错误、ST 表构建错误、偏移错误等几乎所有问题。平时练习不要怕写暴力，暴力是检查思维盲区最好的尺子。

5. 从括号配对到单调栈，栈的套路其实没有变

5.1 括号画家、最长合法子串和同一双“做题之眼”

研究完 P8430 这类题，你会发现很多括号题只需要改一点点题目背景，就成了另一道题。

比如著名的“最长合法括号子段”，给定串)()())，要返回最长连续合法括号长度。这类题也可以用栈做，但细节会变化。一个常见做法是：遇到右括号并成功匹配左括号时，当前合法长度不仅包含这一对括号，还要向前合并之前已经合法的部分。比如()()中第二个括号匹配完，长度应该是 4 而不是 2。为了合并前面的合法段，你需要知道“前一个未匹配位置的下标”，并不断按匹配情况刷新答案。你会发现，栈里保存下标这个习惯，在这里直接帮你建立了合并区间的基础。

再比如把括号从一种变成三种，加一个“相邻不同括号不允许交叉匹配”的限制，就成了括号画家类题目。改法也不难，遇到右括号时检查栈顶左括号是否与当前右括号种类匹配，不匹配直接判非法。核心逻辑还是那套“用栈保留下标/字符，按顺序消除”的思维。

所以我的建议是：刷括号题时，不要只记代码，多做一件额外的事——问自己“栈里存了什么信息，为什么存这个信息”。如果栈里存字符，是为了判断种类是否正确；如果存下标，是为了能回答区间、长度、配对关系；如果存计数，通常只是偷懒版的合法判断。积累多了，新题也能靠这双眼睛快速归类。

5.2 单调栈并没有那么神秘，它只是换了一条弹出规则

说完括号题，再说说洛谷上另一大类栈题——单调栈。不少人觉得括号栈和单调栈是两个流派，其实它们底层都是同一个数据结构，区别只在于“什么时候弹出”。

括号匹配里，遇到右括号时弹出栈顶左括号；单调栈里，遇到破坏单调性的当前元素，弹出所有比它小或比它大的栈内元素。二者都在维护一个“按顺序到达、但还未被解决”的候选集合。经典题“下一个更大元素”就是从右往左扫时维护一个从栈底到栈顶递减的栈，每次弹出所有比当前元素小的元素后，栈顶就是答案。

认真做过 P8430 后再学单调栈，你的理解会更顺：原来栈不是为括号题发明的，而是所有“需要回头看左边某个未处理元素”的问题都会想到它。括号题的左括号是“等待被右括号处理”，单调栈里的旧元素是“等待被更大/更小的新元素处理”，本质同构。

现在很多人口中的“技术栈”，早就不单指数据结构了，更多是说全栈项目里语言、框架、工具层层叠起来的那一套组合。但算法题里的栈，感情比这个朴素得多：它只需要你回答，“当前位置的左边，有没有哪些信息是以后还会被用到的？如果会，应该按什么顺序取出来？”括号题就是一个最好的例子。

如果让我给正在做 P8430 的人一个建议，我会说：别急着把代码背下来，先拿笔模拟一个长度为 8 的括号串，亲手把每次入栈、弹栈、match 数组的变化写一遍。栈的操作不需要背，多模拟几次，你会发现它不过是一个“从里往外拆括号”的过程，拆明白了，题目也就做明白了。