LeetCode 32 Longest Valid Parentheses：棧與索引法求最長有效括號子串

題目簡介

給定只含 '(' 和 ')' 的字符串，求最長有效（匹配良好）括號子串長度。例如 "(()" → 2，")()())" → 4。

解法一：暴力遞減長度檢查（超時）

從最大偶數長度開始，枚舉所有子串，用棧判斷是否有效。時間 O(n^3)，不可行。

解法二：棧保存索引（O(n)）

用棧存儲未匹配字符的索引。初始壓入 -1 作為邊界。遍歷字符串：

• 遇到 '(' 或無法匹配時，壓入當前索引。
• 遇到 ')' 且棧頂為 '(' 時，彈出棧頂。

遍歷結束後，棧中剩餘索引即為分隔各有效段的邊界。相鄰索引差減 1 即為有效段長度，取最大值。

代碼實現

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

複雜度分析

時間 O(n)，空間 O(n)。比暴力法快數量級（1ms vs 1790ms）。