LeetCode 32: Longest Valid Parentheses — 最長有效括號子串的三種 O(n) 解法

題目大意

給定只含 '(' 和 ')' 的字串，找出最長的**合法括號子串**長度。合法定義：每個左括號有對應右括號且巢狀正確。

範例："(()" → 2 ("()")；")()())" → 4 ("()()")。

解法一：棧 + 索引記錄 (最直觀)

棧存**未匹配的左括號索引**，遇到右括號彈出；若棧空說明當前右括號無匹配，記錄其索引作為「新起點」。

int longestValidParentheses(string s) {
    stack st;
    st.push(-1);  // 虛擬邊界
    int maxlen = 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 maxlen = max(maxlen, i - st.top());
        }
    }
    return maxlen;
}

解法二：動態規劃 DP

dp[i] 表示**以 i 結尾**的最長有效子串長度。

int longestValidParentheses(string s) {
    int n = s.size(), maxlen = 0;
    vector dp(n, 0);
    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i-1] == '(') {                    // 情況 1: ...()
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            } else if (i - dp[i-1] > 0 &&           // 情況 2: ...))
                       s[i - dp[i-1] - 1] == '(') {
                dp[i] = dp[i-1] + 2 + 
                        (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0);
            }
            maxlen = max(maxlen, dp[i]);
        }
    }
    return maxlen;
}

解法三：雙向掃描計數器 (O(1) 空間)

左→右掃描計數 left, right，相等時更新答案；right > left 重置。再右→左掃描處理 left > right 的遺漏情況 (如 "(()")。

int longestValidParentheses(string s) {
    int maxlen = 0, left = 0, right = 0;
    // 左→右
    for (char c : s) {
        if (c == '(') left++; else right++;
        if (left == right) maxlen = max(maxlen, 2*right);
        else if (right > left) left = right = 0;
    }
    // 右→左
    left = right = 0;
    for (int i = s.size()-1; i >= 0; i--) {
        if (s[i] == '(') left++; else right++;
        if (left == right) maxlen = max(maxlen, 2*left);
        else if (left > right) left = right = 0;
    }
    return maxlen;
}

三解法複雜度對比

關鍵測試用例

總結
「最長有效括號」是棧、DP、貪心雙向掃描三大經典技巧的完美練習題。面試推薦**棧解法** (邏輯最清晰、易現場編寫)；追求極致空間效率用**雙向掃描**；DP 解法適合展示動態規劃思維。掌握三種解法可應對各種變體 (如輸出子串、多種括號、帶權重等)。