LeetCode Longest Valid Parentheses：棧 + DP 雙解法

題目大意

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

方法一：棧記錄索引 + 掃描合併

1. 遍歷字串，遇 '(' 入棧索引；遇 ')' 若棧非空，彈出匹配的 '(' 索引，記錄該匹配對長度 len = i - left + 1 存入 match[i] = len。
2. 從右向左掃描 match 陣列：若 match[i] > 0，累加長度並跳至匹配左括號前一位 j = i - match[i]；若 match[j] > 0 則繼續合併。維護最大值。

方法二：布爾陣列標記 + 最長連續 True

1. 同樣用棧匹配，但用 bool valid[n] 標記匹配位置為 true。
2. 最終問題轉化為：求 valid 中最長連續 true 段長度。因為匹配對內部必全匹配，此法正確且簡潔。

代碼實現（方法二）

public int longestValidParentheses(String s) {
    if (s.isEmpty()) return 0;
    Stack<Integer> st = new Stack<>();
    boolean[] valid = new boolean[s.length()];
    for (int i = 0; i < s.length(); ++i) {
        if (s.charAt(i) == '(') st.push(i);
        else if (!st.isEmpty()) {
            valid[i] = valid[st.pop()] = true;
        }
    }
    int maxLen = 0, cur = 0;
    for (boolean v : valid) {
        if (v) maxLen = Math.max(maxLen, ++cur);
        else cur = 0;
    }
    return maxLen;
}

複雜度

• 時間：O(n)，單次遍歷 + 掃描。
• 空間：O(n)（棧 + 輔助陣列）。

關鍵洞察

一對匹配括號內部的字串必然也是合法的（或為空），因此匹配區間內所有字符都屬於同一合法子串。這使得「標記匹配位 → 求最長連續 True」等價於原問題。

範例

輸入: "(()"        輸出: 2  (子串 "()")
輸入: ")()())"     輸出: 4  (子串 "()()")