秋招知识库

主题

题目链接 · 灵神原题解（署名来源）

什么是有效括号？ ​

可以从消消乐的角度理解，每次消除一对相邻的左括号和右括号，不断消除，如果最终变成空串，则（消除之前）是有效括号。

比如 (), ()(), (()), (())() 等等，都可以通过消除，变成空串。

什么不是有效括号？ ​

  1. 某些左括号没有对应的右括号。例如 (()，缺失了一个右括号。
  2. 某些右括号没有对应的左括号。例如 ())，缺失了一个左括号。

栈 + 配对标记 ​

从左到右遍历字符串 s，对于右括号，找左侧最近的未配对的左括号，然后把这一对括号标记为「已配对」。

为方便找到左侧最近的未配对的左括号，我们可以用一个栈保存遍历过的左括号的下标：

  • 遇到左括号，把其下标入栈。
  • 遇到右括号，且栈非空，那么弹出栈顶。这样遍历到下一个右括号时，栈顶总是最近的未配对的左括号的下标。

最后，最长连续已配对标记的长度，就是最长有效括号的长度。做法同 485. 最大连续 1 的个数，我的题解。

python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        is_valid = [False] * n
        st = []  # 未配对的左括号的下标

        # 标记哪些括号是配对的
        for i, ch in enumerate(s):
            if ch == '(':
                st.append(i)  # 保存左括号的下标
            elif st:  # 右括号与栈顶的左括号配对
                is_valid[i] = is_valid[st.pop()] = True

        # 最长有效括号即为 is_valid 中的最长连续 True
        ans = cnt = 0
        for b in is_valid:
            if b:
                cnt += 1  # 连续 True 的个数
                ans = max(ans, cnt)
            else:
                cnt = 0  # 重置计数器
        return ans
cpp
// C++ 版待补充
cpp
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int8_t> is_valid(n);
        stack<int> st; // 未配对的左括号的下标

        // 标记哪些括号是配对的
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                st.push(i); // 保存左括号的下标
            } else if (!st.empty()) { // 右括号与栈顶的左括号配对
                is_valid[i] = is_valid[st.top()] = true;
                st.pop();
            }
        }

        // 最长有效括号即为 is_valid 中的最长连续 true
        int ans = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (is_valid[i]) {
                cnt++; // 连续 true 的个数
                ans = max(ans, cnt);
            } else {
                cnt = 0; // 重置计数器
            }
        }
        return ans;
    }
};

复杂度分析 ​

  • 时间复杂度：O(n)，其中 n 是 s 的长度。
  • 空间复杂度：O(n)。

优化：一次遍历 ​

既然栈中保存的是未配对的下标，那么从栈顶加一的位置到 i，就是已配对的连续括号，长度为 i 减去栈顶，更新答案的最大值。

特殊情况：

  1. 例如 s=)()，其中 s[0] 是永远无法配对的右括号。把这种括号的下标入栈，从而保证「栈顶加一」是有效括号的左端点。
  2. 如果栈为空呢？此时有效括号的左端点是 0。我们可以在一开始，往栈中添加一个 −1，这样可以兼容「栈顶加一」是有效括号的左端点，从而简化代码逻辑。
python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        st = [-1]  # 未配对括号的下标，其中栈底元素表示永远无法配对的括号下标
        ans = 0

        for i, ch in enumerate(s):
            if ch == '(':
                st.append(i)  # 保存左括号的下标
            elif len(st) > 1:
                st.pop()  # 右括号与栈顶的左括号配对
                ans = max(ans, i - st[-1])  # 从 st[-1]+1 到 i 都已配对，长为 i - st[-1]
            else:  # s[i] 是永远无法配对的右括号
                st[0] = i  # 替换栈底

        return ans
cpp
// C++ 版待补充
cpp
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 if (st.size() > 1) {
                st.pop(); // 右括号与栈顶的左括号配对
                ans = max(ans, i - st.top()); // 从 st.top()+1 到 i 都已配对，长为 i - st.top()
            } else { // s[i] 是永远无法配对的右括号
                st.top() = i; // 替换栈底
            }
        }

        return ans;
    }
};

复杂度分析 ​

  • 时间复杂度：O(n)，其中 n 是 s 的长度。
  • 空间复杂度：O(n)。

优化：O(1) 空间复杂度 ​

对于有效括号字符串，左括号和右括号的个数是相等的。

能不能只记录左右括号的个数，并在左括号个数等于右括号个数时，更新答案？

比如 s=())()，从左到右遍历：

is[i]左括号个数右括号个数说明
0(10
1)11个数相同，有效括号长度为 2
2)00右括号太多了，重置个数为 0
3(10
4)11个数相同，有效括号长度为 2

又比如 s=()(()，从左到右遍历：

is[i]左括号个数右括号个数说明
0(10
1)11个数相同，有效括号长度为 2
2(21
3(31
4)32无法判断有效括号长度（见下面解释）

设 left 为左括号的个数，right 为右括号的个数，分类讨论：

  • 如果 left=right，有效括号长度为 right⋅2。
  • 如果 left<right，右括号太多了，重置计数器 left=right=0。
  • 如果 left>right，我们无法只根据 left 和 right 就确定有效括号的长度。比如 left=3，right=2，那么 s 是 ((()) 还是 ()(()？有效括号长为 4 还是 2？如何解决 left>right 这种左括号很多的情况呢？

把 s 旋转 180∘，多出来的左括号就移到了后面，比如 ((()) 变成 (()))。这样我们就能甩掉红色括号的干扰，在遍历过程中遇到 left=right=2 的情况，成功算出答案 4。所以再倒着遍历一遍 s，就不会算漏了。

python
class Solution:
    def solve(self, s: Iterable[str], left_ch: str) -> int:
        ans = left = right = 0
        for ch in s:
            if ch == left_ch:
                left += 1
            else:
                right += 1
            if left < right:  # 右括号太多了，重置计数器
                left = right = 0
            elif left == right:
                ans = max(ans, right * 2)
        return ans

    def longestValidParentheses(self, s: str) -> int:
        return max(self.solve(s, '('), self.solve(reversed(s), ')'))  # reversed 是 O(1) 的
cpp
// C++ 版待补充
cpp
class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0, left = 0, right = 0;
        for (char ch : s) {
            if (ch == '(') {
                left++;
            } else {
                right++;
            }
            if (left < right) { // 右括号太多了，重置计数器
                left = right = 0;
            } else if (left == right) {
                ans = max(ans, right * 2);
            }
        }

        left = right = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == ')') {
                left++;
            } else {
                right++;
            }
            if (left < right) {
                left = right = 0;
            } else if (left == right) {
                ans = max(ans, right * 2);
            }
        }
        return ans;
    }
};

复杂度分析 ​

  • 时间复杂度：O(n)，其中 n 是 s 的长度。
  • 空间复杂度：O(1)。

专题训练 ​

见下面数据结构题单的「§3.4 合法括号字符串」。

分类题单 ​

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

本文整理自灵茶山艾府（endlesscheng）的公开内容，仅供个人学习使用
本站为个人秋招复习知识库 · 仅供个人学习使用

本站仅供个人学习使用，请勿外传

秋招知识库