最长有效括号

题目描述

LeetCode 32 — 最长有效括号 (Hard)

给你一个只包含 '(' 和 ')' 的字符串 s，请找出其中最长的有效（格式正确且连续）括号子串的长度。左右括号匹配，即每个左括号都有对应的右括号将其闭合。

示例 1：

• 输入：s = "(()"
• 输出：2
• 解释：最长有效括号子串是 "()"。

示例 2：

• 输入：s = ")()())"
• 输出：4
• 解释：最长有效括号子串是 "()()"。

示例 3：

• 输入：s = ""
• 输出：0

约束：

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

---

求解思路：栈

括号是否匹配取决于左括号和右括号的先后关系，因此从左到右扫描时，用栈保存尚未匹配的位置，就能在遇到右括号时找到它可能匹配的左括号。栈里保存下标而不是字符，是因为题目最终要求的是连续子串长度。

先把 -1 放入栈作为初始边界。遇到左括号，就把它的下标压栈，表示它尚未匹配。遇到右括号时，先弹出栈顶，尝试用它匹配当前右括号；如果弹出后栈为空，说明当前右括号左侧没有可匹配的边界，它本身就成为新的边界位置并压入栈中。否则，栈顶就是当前有效括号子串之前最近的未匹配位置，当前有效后缀长度便是 i - st.top()。

每一步都用这个长度更新答案。初始的 -1 让从字符串开头开始的有效子串也能直接通过下标相减得到长度；遇到无法匹配的右括号后，新的边界则避免把它之前的字符计入后续结果。

解法：栈记录边界下标

/*
遇'('压栈，遇')'弹出，初始栈内放-1，若弹出后栈空则压入当前右括号下标
最后长度为栈顶减去栈底
*/
#include <vector>
#include <string>
#include <stack>

using namespace std;

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

复杂度： 时间 $O(n)$，每个下标最多入栈、出栈一次；空间 $O(n)$，最坏情况下栈中会保存所有左括号下标。

---

相关题目

• LeetCode 20 — 有效的括号（括号匹配与栈）
• LeetCode 22 — 括号生成（生成所有有效括号序列）
• LeetCode 301 — 删除无效的括号（处理无效括号）
• LeetCode 856 — 括号的分数（利用括号结构计算分数）