解題說明
Longest Valid Parentheses
題目描述：給定一個只包含 '(' 和 ')' 的字串，找出最長的有效（格式正確且連續）括號子字串的長度。
解題思路：我們介紹最直觀的堆疊法。
維護一個堆疊，初始放入哨兵值 -1（代表「上一個無效位置的索引」）。
遍歷每個字元：
- 若是
'('：將其索引壓入堆疊。 - 若是
')'：- 先彈出堆疊頂部（配對最近的
'('或哨兵）。 - 若堆疊為空，將當前索引壓入作為新的哨兵（代表新的「無效邊界」）。
- 若堆疊不為空，當前有效子字串長度 = 當前索引 − 堆疊頂部索引，更新最大值。
- 先彈出堆疊頂部（配對最近的
為什麼初始放 -1？ 因為若字串一開始就是有效的（如 "()"），彈出哨兵後堆疊為空，長度 = 1 − (−1) = 2，恰好正確。
DP 方法補充：定義 dp[i] = 以 s[i] 結尾的最長有效括號長度。若 s[i] = ')'：若 s[i-1] = '('，則 dp[i] = dp[i-2] + 2；若 s[i-1] = ')' 且 s[i - dp[i-1] - 1] = '('，則 dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2。
C++ 解法
複雜度分析
時間複雜度：O(n) — 無論是堆疊法還是 DP 法，都只需一次從左到右的線性掃描，每個字元恰好處理一次。
空間複雜度：O(n) — 堆疊法最壞情況下（全是 '('）堆疊深度為 n；DP 法需要 O(n) 的 dp 陣列。若使用雙指標計數法（Two-Pass Counter）可達到 O(1) 空間。
虛擬碼
Stack approach:
1. Initialize stack with sentinel value -1
2. Set maxLen = 0
3. For each index i from 0 to n-1:
a. If s[i] == '(': push i onto stack
b. Else (s[i] == ')'):
- Pop top of stack
- If stack is empty: push i as new sentinel
- Else: maxLen = max(maxLen, i - stack.top())
4. Return maxLen
DP approach:
1. Initialize dp[0..n-1] = 0, maxLen = 0
2. For i from 1 to n-1:
a. If s[i] == ')':
- If s[i-1] == '(': dp[i] = dp[i-2] + 2 (if i>=2, else 2)
- Else if dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] (if index valid)
- maxLen = max(maxLen, dp[i])
3. Return maxLen其他解法
方法一：動態規劃（Dynamic Programming）
定義 dp[i] 為以索引 i 結尾的最長有效括號子字串長度。透過分析 s[i] 和 s[i-1] 的字元組合推導遞推公式。時間複雜度 O(n)，空間複雜度 O(n)。優點是邏輯清晰，但需要仔細處理邊界索引。
方法二：雙向掃描計數法（Two-Pass Left-Right Counter）
從左到右掃描，用 left 和 right 計數器分別統計 '(' 和 ')' 的數量：當兩者相等時更新最大長度；當 right > left 時重置兩者。再從右到左做一次相同操作（角色互換）。兩遍掃描合起來覆蓋所有情況。時間複雜度 O(n)，空間複雜度 O(1)，是空間最優解。
延伸思考
- 雙向掃描計數法（Two-Pass Counter）如何在不使用任何額外空間的情況下得到正確答案？為什麼需要從兩個方向各掃描一次？
- 如果題目改為找最長有效括號子序列（不要求連續），解法會有何不同？時間複雜度是否仍可達 O(n)？
- 本題只有
(和)兩種括號，若同時包含(、)、[、]、{、}三種括號，如何找最長有效括號子字串？