32. 最长有效括号

难度：🔴 Hard | 标签：动归、栈 | 状态：⬜ LeetCode 链接

思路

栈法最直观：

• 栈底始终是「最近一个不匹配的位置」（初始放 -1）
• ( 压下标
• ) 先弹，弹完若栈空则把当前 i 压入作为新基准；否则 i - 栈顶 是当前有效长度

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int best = 0;
        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 best = max(best, i - st.top());
            }
        }
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(n)

易错 / 回顾

• 初始压 -1 作哨兵
• 弹空后压当前 i（开启新段基准）
• DP 解：dp[i] 以 i 结尾的最长有效，分 s[i]=')' 时 s[i-1]=='(' 或 '(' 的两种情况