LeetCode 32 最長有效括號：棧 + 單次掃描 O(N) 解法

LeetCode 32 最長有效括號：棧 + 單次掃描 O(N) 解法

給定只含 '(' 和 ')' 的字符串，求最長合法括號子串長度。例："(()" → 2，")()())" → 4。

棧法核心思想

棧存未匹配的左括號索引，輔助變量 start = -1 記錄「上一個未匹配右括號的位置」。遍歷字符串：

• '('：索引入棧
• ')'：
  • 棧非空：彈出匹配左括號。若棧空 → 當前有效長度 = i - start；若棧非空 → 長度 = i - stack.top()
  • 棧空：無左括號匹配，更新 start = i

Java 代碼

public int longestValidParentheses(String s) {
    if (s == null || s.isEmpty()) return 0;
    Deque<Integer> stack = new ArrayDeque<>();
    int start = -1, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            if (!stack.isEmpty()) {
                stack.pop();
                if (stack.isEmpty()) maxLen = Math.max(maxLen, i - start);
                else maxLen = Math.max(maxLen, i - stack.peek());
            } else {
                start = i;
            }
        }
    }
    return maxLen;
}

關鍵點解析

• start 標記「最後一個無法匹配的右括號」，作為有效子串的左邊界
• 棧空時，說明從 start+1 到 i 完全匹配
• 棧非空時，棧頂是「當前未匹配的最左左括號」，有效子串從其右側開始
• 單次遍歷，時間 O(N)，空間 O(N)

對比 DP 解法

DP 定義 dp[i] = 以 i 結尾的最長有效長度，轉移較繁瑣。棧法更直觀、代碼更短。