32. 最长有效括号

发表于 分类于 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

  • 栈
  • 线性DP

思路

一、先把“连续有效括号子串”想明白

在开始任何算法之前，必须先明确：我们到底在找什么东西。

1. 什么叫“连续”

“连续”意味着： 只能取字符串中的一整段区间，不能跳字符。

例如字符串：

1
s = "()(()())())"

下面这些都是连续子串（substring）：

  • "()"
  • "(()())"
  • "()(()())()"
  • "())"（虽然不合法，但它是连续的）

2. 什么叫“有效括号串”

一个括号串是有效的，只有两种“基本形态”，以及它们的组合：

（1）并列型（平铺型）

形如：

1
()()()

特点：

  • 每一对括号都是“并排”的
  • 没有嵌套
  • 可以理解为：() 的重复拼接

（2）嵌套型

形如：

1
((()))

特点：

  • 括号一层包一层
  • 先开的后关
  • 所有 ')' 都在最后一段

（3）并列 + 嵌套的组合

例如：

1
2
3
(()())
()(())
(()(()))

可以把它们理解为：

  • 外层是嵌套
  • 内层可能是并列
  • 或多个合法块拼接在一起

结论一句话：

任意一个有效括号串，一定是由

  • 若干个 "()"
  • 通过“并列”或“嵌套”方式组合而成

3. 本题真正要做的事

给定整个字符串 s，我们要做的是：

在所有连续子串中，找一个

  • 本身是有效括号串
  • 长度最大的那个

注意： 不是求有多少对括号，而是求一整段的长度。

二、为什么“断点”是问题的核心

来看一个例子：

1
s = ")()())"

从左往右看：

位置 字符 说明
0 ) 一上来就关，必然非法
1 ( 新开始
2 ) 匹配成功，得到 "()"
3 ( 新开始
4 ) 又匹配成功
5 ) 没有可匹配的 '('，非法

这里有两个非常重要的“断裂点”：

  • 第 0 位的 ')'
  • 第 5 位的 ')'

任何跨过断点的区间，都不可能是合法的连续括号子串。

这正是栈解法和 DP 解法都在解决的核心问题：

如何正确地“切断”不可能继续扩展的区间。

三、栈解法：用下标划分“连续合法区间”

1. 栈里到底放什么？

栈里只放下标，而且下标有两种含义：

  1. 还没被匹配的 '(' 的位置
  2. 断点位置（无法匹配的 ')'）

为了统一处理，我们在一开始放入一个特殊下标：

1
-1

它表示：

在字符串最左边之前，有一个“虚拟断点”。

2. 遍历时的直观逻辑

从左到右扫描字符串，对每个字符：

情况 1：遇到 '('

1
(  ← 可能会被未来的 ')' 匹配
  • 把它的下标压入栈
  • 等待后续 ')' 来匹配

情况 2：遇到 ')'

先做一件事：

尝试匹配一个 '('

也就是：

1
st.pop()

然后分两种情况：

（1）栈空了

说明：

  • 当前这个 ')' 没有任何 '(' 可以匹配
  • 它本身就是一个新的断点

做法：

1
把当前下标 i 压入栈
（2）栈没空

说明：

  • 找到了一个合法的匹配
  • 当前可以形成一个以 i 结尾的连续有效区间

此时：

1
当前有效长度 = i - st.top()

为什么对？

  • st.top() 永远指向：
    • 上一个“无法被纳入当前区间的下标”
  • 从 st.top() + 1 到 i：
    • 一定是连续的
    • 一定是合法的

3. 栈解法代码（含注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);                // 初始断点
        int ans = 0;

        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                // 记录一个可能被匹配的 '('
                st.push(i);
            } else {
                // 尝试匹配一个 '('
                st.pop();

                if (st.empty()) {
                    // 没有可匹配的 '('，当前 ')' 成为新的断点
                    st.push(i);
                } else {
                    // 以 i 结尾的连续合法区间
                    ans = max(ans, i - st.top());
                }
            }
        }
        return ans;
    }
};

4. 栈解法的本质总结

栈解法并不是在“匹配括号”， 而是在 维护连续合法区间的左边界。

四、DP 解法：直接问“到这里为止能有多长”

1. DP 状态的直观含义

定义： \[ f[i] = \text{以第 } i \text{ 个字符结尾的最长有效括号子串长度} \] 强调两点：

  • 必须以 i 结尾
  • 只关心“到这里为止”

2. 为什么只有 ')' 才可能更新

如果：

1
s[i] == '('

那以它结尾：

  • 不可能是合法括号串
  • 所以：

\[ f[i] = 0 \]

3. 两种能形成合法串的形态

情况 1：直接配对 "()"

形态：

1
...()

也就是：

1
2
s[i-1] == '('
s[i]   == ')'

此时：

  • 新增一对 ()
  • 再接上前面的合法串

\[ f[i] = f[i-2] + 2 \]

情况 2：嵌套或组合 "...))"

形态：

1
...))

例如：

1
(()))

思路：

  1. 已知：

\[ f[i-1] = k \]

表示前面那一段已经是合法的

  1. 那么它的起点是：

\[ i - k \]

  1. 如果在它前面紧挨着有一个 '('：

\[ s[i-k-1] == '(' \]

就能形成新的匹配：

1
( [合法长度 k] )

还可以再往前接一段： \[ f[i] = f[i-1] + 2 + f[i-k-2] \]

4. DP 解法代码（含注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    static const int maxn = 3e4 + 5;

    int longestValidParentheses(string s) {
        int f[maxn];
        int n = s.size();
        int res = 0;

        // f[i]：以第 i 个字符结尾的最长有效括号子串长度
        // 使用 1-based，下标 i 对应 s[i-1]
        f[0] = f[1] = 0;

        for (int i = 2; i <= n; ++i) {
            f[i] = 0;

            // '(' 结尾不可能合法
            if (s[i - 1] == '(')
                continue;

            // 情况 1："...()"
            if (s[i - 2] == '(') {
                f[i] = f[i - 2] + 2;
            }
            // 情况 2："...))"
            else {
                int idx = i - 1 - f[i - 1];
                if (idx > 0 && s[idx - 1] == '(') {
                    f[i] = f[i - 1] + 2 + f[idx - 1];
                }
            }
            res = max(res, f[i]);
        }
        return res;
    }
};