括号序列专题 (Parentheses Sequences)¶
括号序列是算法竞赛和工程面试中极其高频的核心模型。它不仅是栈（Stack）结构的经典载体，更是深刻连接了前缀和折线理论（Dyck 路径）、卡特兰数（Catalan Number）组合计数、动态规划、括号树与森林同构以及线段树区间不可逆信息合并的经典综合专题。
1. 核心数学原理与合法性充要条件¶
1.1 单类型括号序列：前缀和与 Dyck 路径¶
对于仅由 '(' 和 ')' 构成的长度为 \(2n\) 的括号序列 \(s\)：
为字符赋予权值：\(val('(') = +1\)，\(val(')') = -1\)。
定义前缀和序列 \(S_i = \sum_{k=1}^i val(s[k])\)（约定 \(S_0 = 0\)）。
充要条件定理： 序列 \(s\) 是合法括号序列（Valid Parentheses），当且仅当满足以下两个条件：
- 非负性前缀不变量：对任意前缀位置 \(1 \le i \le 2n\)，均有 \(S_i \ge 0\)（在任意时刻，右括号的数量不能严格超过左括号）；
- 零终态闭合性：\(S_{2n} = 0\)（序列结束时，左括号和右括号的总数量严格相等）。
网格折线视角（Dyck Path）：
将前缀和的变化轨迹绘制在二维直角坐标系中（从 \((0, 0)\) 出发，遇到 '(' 走向量 \((1, 1)\)，遇到 ')' 走向量 \((1, -1)\)）。合法括号序列等价于从 \((0, 0)\) 出发到达 \((2n, 0)\)，且整条轨迹始终不穿过横轴下方（\(y \ge 0\)）的格路。
// 基础校验：单类型括号合法性检查
bool isValidSingle(const std::string &s) {
int balance = 0;
for (char c : s) {
if (c == '(') {
balance++;
} else if (c == ')') {
balance--;
if (balance < 0) return false; // 任意时刻右括号超额即非法
}
}
return balance == 0;
}
1.2 多类型括号序列：后进先出 (LIFO) 栈消消乐¶
当序列中混合出现多种括号（如 (), [], {}）时，仅靠计数器前缀和无法解决交叉嵌套破坏结构的问题（例如 ([)] 虽满足各类括号数量守恒，但结构非法）。
消消乐归约定理： 一个多类型括号序列合法，当且仅当可以不断消除相邻的同类型匹配括号对（如消除
()、[]、{}），最终化简为空串。 栈作为后进先出（LIFO）容器，每次遇到左括号压栈；遇到右括号时，栈顶必须是同类型的对应左括号，否则立刻判定非法。
#include <string>
#include <stack>
#include <unordered_map>
bool isValidMultiple(const std::string &s) {
std::stack<char> st;
std::unordered_map<char, char> matching = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
if (matching.count(c)) {
// 遇到右括号：栈不能为空，且栈顶必须匹配
if (st.empty() || st.top() != matching[c]) {
return false;
}
st.pop();
} else {
// 遇到左括号：压栈
st.push(c);
}
}
return st.empty();
}
1.3 带通配符括号匹配：贪心可行区间维护¶
当序列中引入可替代为 '('、')' 或空字符 "" 的通配符 '*' 时（例如 LeetCode 678），未匹配的左括号数量不再是一个固定数值，而是一个连续的整数区间 \([low, high]\)。
连续可行区间引理： 遍历过程中，所有可能的未匹配左括号数必然构成一段连续的整数闭区间 \([low, high]\)：
- 遇到
'('：\(low \leftarrow low + 1, \, high \leftarrow high + 1\)；- 遇到
')'：\(low \leftarrow \max(0, low - 1), \, high \leftarrow high - 1\)；- 遇到
'*'：
- 若视为
'('：\(high \leftarrow high + 1\)；- 若视为
')'：\(low \leftarrow \max(0, low - 1)\)；- 若视为空串：维持不变。
- 综合转移：\(low \leftarrow \max(0, low - 1), \, high \leftarrow high + 1\)。
若在任意时刻出现 \(high < 0\)，说明即使把所有的
'*'全变成左括号，右括号依然超标，直接判定非法；遍历结束时只要 \(low == 0\)，说明可以通过合适选择让多余左括号全被抵消，判定合法。
bool checkValidString(const std::string &s) {
int low = 0, high = 0;
for (char c : s) {
if (c == '(') {
low++;
high++;
} else if (c == ')') {
low = std::max(0, low - 1);
high--;
if (high < 0) return false; // 必有无法匹配的多余右括号
} else { // c == '*'
low = std::max(0, low - 1);
high++;
}
}
return low == 0;
}
2. 卡特兰数与合法序列生成¶
2.1 卡特兰数公式与几何折线法证明¶
由 \(n\) 对 '(' 和 ')' 构成的长度为 \(2n\) 的不同合法括号序列的总数，严格等于第 \(n\) 项卡特兰数（Catalan Number）\(C_n\)：
前若干项为：\(C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, \dots\)
反射原理（Reflection Principle）几何证明：
- 从 \((0, 0)\) 到达 \((2n, 0)\) 的任意路径总数等于在 \(2n\) 步中任选 \(n\) 步向上，共有 \(\binom{2n}{n}\) 条；
- 凡是不合法的路径，必然在某个时刻首次触碰直线 \(y = -1\)；
- 将路径在首次触碰 \(y = -1\) 之后的部分关于直线 \(y = -1\) 作对称翻转。对称后的终点必然从 \((2n, 0)\) 映射到 \((2n, -2)\)；
- 终点在 \((2n, -2)\) 的路径由 \(n - 1\) 步向上和 \(n + 1\) 步向下组成，总数为 \(\binom{2n}{n + 1}\)；
- 因此所有非法路径与到达 \((2n, -2)\) 的路径建立了一一双射。合法路径数即为：\(C_n = \binom{2n}{n} - \binom{2n}{n + 1} = \frac{1}{n + 1} \binom{2n}{n}\)。
2.2 回溯生成合法括号组合¶
通过回溯搜索生成所有合法括号组合时（LeetCode 22），必须遵循前缀平衡剪枝铁律：
- 只要当前放入的左括号数 \(open < n\)，就可以放入
'('； - 只要当前放入的右括号数 \(close < open\)，就可以放入
')'； - 绝不会搜索到任何非法状态，搜索树的叶子节点数恰好等于 \(C_n\)。
#include <vector>
#include <string>
std::vector<std::string> generateParenthesis(int n) {
std::vector<std::string> result;
std::string current;
auto backtrack = [&](auto &self, int open, int close) -> void {
if ((int)current.size() == 2 * n) {
result.push_back(current);
return;
}
if (open < n) {
current.push_back('(');
self(self, open + 1, close);
current.pop_back();
}
if (close < open) {
current.push_back(')');
self(self, open, close + 1);
current.pop_back();
}
};
backtrack(backtrack, 0, 0);
return result;
}
3. 最长有效括号子串的三大解法¶
给定一个仅包含 '(' 和 ')' 的字符串，求最长的连续合法括号子串的长度（LeetCode 32）。该题有三大经典解法：
3.1 解法一：下标基准栈（最常用）¶
- 栈底维护一个“最后一个未匹配右括号的下标基准点”（初始压入虚拟基准 \(-1\)）；
- 遍历下标 \(i\)：
- 遇到
'('：将其下标 \(i\) 压入栈； - 遇到
')'：先弹出栈顶；- 若栈为空：说明当前
')'没有匹配的左括号，该位置成为新的“未匹配右括号基准点”，将当前下标 \(i\) 压入栈底； - 若栈非空：当前有效子串的长度就是 \(i - \text{st.top()}\)，更新全局最大值。
- 若栈为空：说明当前
- 遇到
int longestValidParentheses_Stack(const std::string &s) {
int max_len = 0;
std::stack<int> st;
st.push(-1); // 虚拟基准点
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '(') {
st.push(i);
} else {
st.pop();
if (st.empty()) {
st.push(i); // 新的非法基准点
} else {
max_len = std::max(max_len, i - st.top());
}
}
}
return max_len;
}
3.2 解法二：动态规划¶
设 \(dp[i]\) 表示以字符 \(s[i]\) 结尾的最长有效括号子串的长度。有效子串必然以 ')' 结尾，故当 \(s[i] == '('\) 时，\(dp[i] = 0\)。
当 \(s[i] == ')'\) 时，考察前一个字符：
-
情况 1：\(s[i - 1] == '('\)（形如
...()）： $\(dp[i] = (i \ge 2 ? dp[i - 2] : 0) + 2\)$ -
情况 2：\(s[i - 1] == ')'\)（形如
...))）： 若 \(s[i - dp[i - 1] - 1] == '('\)，说明越过 \(dp[i - 1]\) 跨度的前一个字符正好与当前 \(s[i]\) 配对： $\(dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 \ge 0 ? dp[i - dp[i - 1] - 2] : 0)\)$
int longestValidParentheses_DP(const std::string &s) {
int n = s.size(), max_len = 0;
std::vector<int> dp(n, 0);
for (int i = 1; i < n; ++i) {
if (s[i] == ')') {
if (s[i - 1] == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
int prev = (i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0;
dp[i] = dp[i - 1] + 2 + prev;
}
max_len = std::max(max_len, dp[i]);
}
}
return max_len;
}
3.3 解法三：正反双向双指针（\(\mathcal{O}(1)\) 空间）¶
利用前缀和计数器，无需额外数组或栈空间：
- 从左到右扫描：统计
left和right。 - 若
right == left：更新有效长度 \(2 \times right\)； - 若
right > left：右括号超标，重置left = right = 0。 - 从右到左扫描：避免漏掉类似
(()这种左括号一直多于右括号的情况。 - 若
left == right：更新有效长度 \(2 \times left\)； - 若
left > right：左括号超标，重置left = right = 0。
int longestValidParentheses_TwoPass(const std::string &s) {
int left = 0, right = 0, max_len = 0, n = s.size();
// 1. 正向扫描
for (int i = 0; i < n; ++i) {
if (s[i] == '(') left++;
else right++;
if (left == right) max_len = std::max(max_len, 2 * right);
else if (right > left) left = right = 0;
}
// 2. 逆向扫描
left = right = 0;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '(') left++;
else right++;
if (left == right) max_len = std::max(max_len, 2 * left);
else if (left > right) left = right = 0;
}
return max_len;
}
4. 括号树的分层、权重与嵌套结构¶
4.1 括号序列与有根森林的同构¶
每一个合法的括号序列，天然对应一棵有根树（或森林）：
- 外层的配对
(和)对应树的一个节点； - 其内部包含的所有配对子序列，对应其直接子节点列表；
- 并列出现的并列括号对（如
()()）对应森林中同级的兄弟节点。
4.2 括号的分数与位权累加 (LC 856)¶
规则：() 得 1 分；AB 得分 \(A + B\)；(A) 得分 \(2 \times A\)。
核心数学观察： 每一个最底层的独立括号对
()，其外部包裹了多少层括号（设当前嵌套深度为 \(d\)），它对全局总分的贡献就是：\[ 1 \times 2^d = 2^d \]全局总分恰好等于所有最内层叶子
()的 \(2^{\text{depth}}\) 之和！无需任何树或栈的递归合并，单遍扫描维护当前深度即可：
int scoreOfParentheses(const std::string &s) {
int score = 0, depth = 0;
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '(') {
depth++;
} else {
depth--;
// 只有当紧邻前一个是 '(' 时，当前 ')' 才是最底层的叶子节点
if (s[i - 1] == '(') {
score += (1 << depth);
}
}
}
return score;
}
5. 竞赛高阶：线段树维护动态括号序列¶
在高级数据结构题目中（如 Codeforces 380C - Sereja and Brackets），题目可能要求：支持动态修改括号字符，并高效回答任意区间 \([L, R]\) 内的最长有效括号匹配长度。
5.1 区间节点信息设计¶
在普通括号匹配中，括号运算具有不可逆性（无法直接做区间减法）。在线段树中，每个节点维护三个核心属性：
match：当前区间内部已经成功配对的括号对数；unmatched_open：当前区间在内部相互抵消后，剩余未匹配的左括号'('数量；unmatched_close：当前区间在内部相互抵消后，剩余未匹配的右括号')'数量。
5.2 区间结合律合并推导 (Push Up)¶
当合并左子区间 \(L\) 与右子区间 \(R\) 时： \(L\) 右侧多出来的未匹配左括号，可以与 \(R\) 左侧多出来的未匹配右括号进行跨区间配对：
合并后的三个属性更新为：
该运算严格满足结合律，单次合并 \(\mathcal{O}(1)\)，可在 \(\mathcal{O}(\log n)\) 时间内完成动态单点修改和区间最长有效长度查询（查询结果为 \(2 \times query(L, R).match\)）。
#include <string>
#include <vector>
#include <algorithm>
struct BracketNode {
int match = 0;
int open = 0; // 未匹配左括号
int close = 0; // 未匹配右括号
static BracketNode merge(const BracketNode &L, const BracketNode &R) {
BracketNode res;
int new_match = std::min(L.open, R.close);
res.match = L.match + R.match + new_match;
res.open = L.open + R.open - new_match;
res.close = L.close + R.close - new_match;
return res;
}
};
class BracketSegmentTree {
int n;
std::vector<BracketNode> tree;
void build(int u, int l, int r, const std::string &s) {
if (l == r) {
if (s[l - 1] == '(') tree[u].open = 1;
else tree[u].close = 1;
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid, s);
build(u << 1 | 1, mid + 1, r, s);
tree[u] = BracketNode::merge(tree[u << 1], tree[u << 1 | 1]);
}
public:
BracketSegmentTree(const std::string &s) : n(s.size()), tree(4 * s.size()) {
build(1, 1, n, s);
}
BracketNode query(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[u];
int mid = (l + r) >> 1;
if (qr <= mid) return query(u << 1, l, mid, ql, qr);
if (ql > mid) return query(u << 1 | 1, mid + 1, r, ql, qr);
return BracketNode::merge(query(u << 1, l, mid, ql, qr),
query(u << 1 | 1, mid + 1, r, ql, qr));
}
int queryMaxMatch(int ql, int qr) {
return 2 * query(1, 1, n, ql, qr).match;
}
};
LeetCode 经典真题精选与题解提示¶
-
LeetCode 20 - 有效的括号 (Valid Parentheses)
简单提示
多类型括号栈匹配基石。
- 遍历字符串，遇左括号入栈。
- 遇右括号时，栈必须非空且栈顶为对应的左括号，弹出匹配；若不匹配或栈空则非法。遍历结束栈须为空。
-
LeetCode 22 - 括号生成 (Generate Parentheses)
中等提示
回溯剪枝与卡特兰数生成。
- 维护当前已放左括号数 \(open\) 和右括号数 \(close\)。
- 只要 \(open < n\) 就可以放
'('；只要 \(close < open\) 就可以放')'。叶子节点总数严格等于第 \(n\) 个卡特兰数 \(C_n\)。
-
LeetCode 32 - 最长有效括号 (Longest Valid Parentheses)
困难提示
栈基准法 / 动态规划 / 双向扫描。
- 栈底常驻“上一个未匹配右括号基准下标”（初值 \(-1\)）。遇到
')'出栈后，若非空，有效长度为 \(i - \text{st.top()}\)；若空则将当前 \(i\) 压入作为新基准。 - 亦可正反双向扫描维护
left与right计数器，实现 \(\mathcal{O}(1)\) 空间。
- 栈底常驻“上一个未匹配右括号基准下标”（初值 \(-1\)）。遇到
-
LeetCode 678 - 有效的括号字符串 (Valid Parenthesis String)
中等提示
带通配符可行连续区间贪心维护。
- 维护未匹配左括号的最小可能数 \(low\) 和最大可能数 \(high\)。
'('使二者均 \(+1\)；')'使 \(low = \max(0, low - 1), high - 1\)；'*'使 \(low = \max(0, low - 1), high + 1\)。- 若途中 \(high < 0\) 立即判假；最终 \(low == 0\) 则为真。
-
LeetCode 856 - 括号的分数 (Score of Parentheses)
中等提示
括号嵌套深度与位权累加。
- 识别最内层的独立叶子对
()：每个内层()在深度 \(d\) 处对全局分数的贡献就是 \(1 \ll d\)。 - 单遍扫描：遇到
'('深度 \(+1\)；遇到')'且前一位是'('时累加 \(1 \ll \text{depth}\)，然后深度 \(-1\)。
- 识别最内层的独立叶子对
-
LeetCode 921 - 使括号有效的最少添加 (Minimum Add to Make Parentheses Valid)
中等提示
贪心统计非法单向偏差。
- 维护未匹配左括号数 \(open\) 和需补全的左括号数 \(ans\)。
- 遇到
'('则 \(open++\)；遇到')'若 \(open > 0\) 则抵消 \(open--\)，否则说明出现了孤立右括号，必须添加左括号 \(ans++\)。 - 最终需添加总数即为 \(ans + open\)。
-
LeetCode 1111 - 有效括号字符串的最大嵌套深度 (Maximum Nesting Depth of Two Valid Parentheses Strings)
中等提示
奇偶深度分流平摊。
- 目标是把原括号序列拆分为两个不相交子序列 A 和 B，使得各自的最大嵌套深度最小化。
- 最优划分策略：根据当前嵌套深度 \(d\) 的奇偶性分配，奇数层分给 A，偶数层分给 B（即令分配数组元素为 \(d \bmod 2\)），两者的嵌套深度均被平摊为 \(\lceil \max(d) / 2 \rceil\)。
-
LeetCode 1249 - 移除无效的括号 (Minimum Remove to Make Valid Parentheses)
中等提示
标记多余括号位置。
- 第一次遍历：遇到多余的右括号（栈为空时）直接在原串标记删除；遇到左括号将其下标入栈。
- 遍历结束后，栈中残余的左括号下标即为多余的左括号，全部标记删除。
- 第二次遍历收集所有未被标记的字符拼接返回。
-
LeetCode 301 - 删除无效的括号 (Remove Invalid Parentheses)
困难提示
最少删除量统计 + 回溯去重。
- 第一步：单遍扫描求出全串必须删除的左括号数 \(l_{rem}\) 与右括号数 \(r_{rem}\)。
- 第二步：回溯尝试删除括号，仅当 \(l_{rem} > 0\) 时可尝试删
'('，当 \(r_{rem} > 0\) 时可尝试删')'。 - 去重剪枝：遇到连续相同的括号时只尝试删除第一个，避免生成重复答案串。