LC 32. 最长有效括号

题目描述

这是 LeetCode 上的 32. 最长有效括号 ，难度为 困难。

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"

输出：2

解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"

输出：4

解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""

输出：0

提示：

• $0 <= s.length <= 3 \times 10^4$
• $s[i]$ 为 '(' 或 ')'

---

栈

从前往后扫描字符串 s。

用 i 来记录当前遍历到的位置，用 j 来记录最近的最长有效括号的开始位置的「前一个位置」。

只对 '(' 进行入栈（入栈的是对应的下标），当遍历到 ')' 的时候，由于栈中只有 '('，所以可以直接弹出一个 '(' 与之匹配（如果有的话）。

再检查栈中是否还有 '('，如果有使用栈顶元素的下标来计算长度，否则使用 j 下标来计算长度。

该做法的本质：栈里只存放待匹配的 ( 符号，虽然这些 ( 在原字符串中的下标不一定连续，但 ( 之间一定为有效括号，因此可以使用栈顶元素作为有效括号的左边界计算长度。

举个 🌰，对于 s = ((())(( 的情况，当整个字符串处理完，栈内剩下的不是所有的 ( 符号（不是 $5$ 个），而是剩余待匹配的 ( 符号（而是 $3$ 个，即从左往右第 $1$、$4$ 和 $5$ 个 (），虽然第 $1$ 和第 $4$ 个 ( 符号在 s 中不连续，但其之间必然是有效括号。

Java 代码：

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> d = new ArrayDeque<>();
        int n = s.length(), ans = 0;
        for (int i = 0, j = -1; i < n; i++) {
            if (s.charAt(i) == '(') {
                d.addLast(i);
            } else {
                if (!d.isEmpty()) {
                    d.pollLast();
                    int top = j;
                    if (!d.isEmpty()) top = d.peekLast();
                    ans = Math.max(ans, i - top);
                } else {
                    j = i;
                }
            }
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> d;
        int n = s.length(), ans = 0;
        for (int i = 0, j = -1; i < n; i++) {
            if (s[i] == '(') {
                d.push(i);
            } else {
                if (!d.empty()) {
                    d.pop();
                    int top = j;
                    if (!d.empty()) top = d.top();
                    ans = max(ans, i - top);
                } else {
                    j = i;
                }
            }
        }
        return ans;
    }
};

Python 代码：

from collections import deque

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        d = deque()
        n, ans, j = len(s), 0, -1
        for i in range(n):
            if s[i] == '(':
                d.append(i)
            else:
                if d:
                    d.pop()
                    top = j
                    if d: top = d[-1]
                    ans = max(ans, i - top)
                else:
                    j = i
        return ans

TypeScript 代码：

function longestValidParentheses(s: string): number {
    const d: number[] = [];
    let n = s.length, ans = 0;
    for (let i = 0, j = -1; i < n; i++) {
        if (s[i] === '(') {
            d.push(i);
        } else {
            if (d.length) {
                d.pop();
                let top = j;
                if (d.length) top = d[d.length - 1]
                ans = Math.max(ans, i - top);
            } else {
                j = i;
            }
        }
    }
    return ans;
};

• 时间复杂度：每个字符最多进栈和出栈一次，复杂度为 $O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.32 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。