給定只含
'('與')'的字串，求最長「有效（格式正確且連續）」括號子字串的長度。
Example:
Input: s = ”(()” Output: 2（”()”）
Input: s = ”)()())” Output: 4（”()()”）
Input: s = "" Output: 0
Intuition
TIP
核心思路：用堆疊存「索引」並放一個基準 -1。每遇 ) 就彈出，若堆疊空了就把當前索引當新基準，否則用 i - 堆疊頂端 算出當前有效長度。
- 堆疊底永遠是「最後一個未匹配位置」的索引（基準）
(→ push 索引；)→ pop，若空則 push 當前索引（新基準），否則i - stack.top即有效長度- 也可用左右計數兩遍掃描達到 O(1) 空間
Approaches
⭐ 1. Stack of Indices + Base -1 — O(n) / O(n)
- Idea: 堆疊維護未匹配位置；有效長度 = 當前索引 − 上一個未匹配位置
- Time:
O(n) - Space:
O(n)- 堆疊
class Solution {
fun longestValidParentheses(s: String): Int {
val stack = ArrayDeque<Int>()
stack.addLast(-1) // 基準
var maxLen = 0
for (i in s.indices) {
if (s[i] == '(') {
stack.addLast(i)
} else {
stack.removeLast()
if (stack.isEmpty()) {
stack.addLast(i) // 沒有可匹配的 '('，當前位置成為新基準
} else {
maxLen = maxOf(maxLen, i - stack.last())
}
}
}
return maxLen
}
}2. Left/Right Count, Two Passes — O(n) / O(1)
- Idea: 正掃計左右括號數，相等就更新；右括號多則歸零。反掃再做一次以涵蓋 ”(((” 的情況
- Time:
O(n) - Space:
O(1)- 不用額外空間
class Solution {
fun longestValidParentheses(s: String): Int {
var maxLen = 0
var left = 0; var right = 0
for (c in s) {
if (c == '(') left++ else right++
if (left == right) maxLen = maxOf(maxLen, 2 * right)
else if (right > left) { left = 0; right = 0 }
}
left = 0; right = 0
for (i in s.indices.reversed()) {
if (s[i] == '(') left++ else right++
if (left == right) maxLen = maxOf(maxLen, 2 * left)
else if (left > right) { left = 0; right = 0 }
}
return maxLen
}
}🔑 Takeaways
- Pattern: 堆疊存「索引」算區段長度（不是存字元）；或雙向計數的貪心
- Key trick: 堆疊底放
-1基準是核心，讓「i − 頂端」直接得到長度；兩遍掃描法要正反各一次才能同時處理(過多與)過多