題目出處
難度
hard
題目分類
String, Dynamic Programming, Stack, Bracket Sequences
2026-10-04 一刷
個人範例程式碼 - 一刷 (2026/10/04)
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1] # 作為左邊界指示器，與存入尚未配對的 ( 位置
best = 0
for i, c in enumerate(s):
if c == '(':
stack.append(i)
else:
stack.pop()
if not stack: # 連最左邊界 -1 或 ) 都被 pop
stack.append(i) # 更新左邊界
else: # pop ( 配對成功
best = max(best, i - stack[-1]) # 算到左邊界的合法範圍
return best
算法說明
使用一個 stack 記錄左邊界與尚未配對的 ( 位置，並依照以下情況維護 stack：
- 一開始先以 [-1] 建立初始左邊界
- 如果出現 (，stack 新增 i
- 如果出現 )，stack 就 pop 最後一個值
2.1. 如果 pop 後 stack 為空，表示連最後一個左邊界也都被 pop，要補一個新的左邊界 i
會出現的情況就是遇到沒有 ( 可配對的「)」的情況。
2.2. 如果 pop 後 stack 不為空，表示 pop 為「(」，是合法情況，
這時候可以透過 i - stack[-1] 計算此位置到 stack[-1]（合法區段起點的前一格，可能是左邊界或尚未配對的 (）的最長合法距離。
pop 出的「(」是與目前這個「)」配對的位置，但例如 ()()，我們可以透過 stack[-1] 找到最遠的合法左邊界。
Time Complexity
O(n)
Space Complexity
O(n) # stack 最大可能存的空間