題目

給定一個只包含 '(' 和 ')' 的字串，返回其中 最長的有效括號子串長度。

範例

Input: "(()"
Output: 2
Explanation: 最長有效括號為 "()"。

Input: ")()())"
Output: 4
Explanation: 最長有效括號為 "()()"。

Input: ""
Output: 0

解題思路

這題可以用 動態規劃 (DP) 或 Stack 來解。
這裡用 Stack 方法解釋，邏輯如下：

初始化 Stack，並放入 -1 作為基準。

遍歷字串：

遇到 '('，把當前索引推入 Stack。

遇到 ')'，彈出 Stack 頂部元素。

如果 Stack 空了，將當前索引放入 Stack。

否則用當前索引減去 Stack 頂部索引，更新最大長度。

最終的最大長度即為答案。

時間複雜度：O(n)，空間複雜度：O(n)。

Java 實作
import java.util.*;

class Solution {
public int longestValidParentheses(String s) {
Stack stack = new Stack<>();
stack.push(-1); // 基準索引
int maxLen = 0;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (c == '(') {
            stack.push(i);
        } else {
            stack.pop();

            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }

    return maxLen;
}

}

心得

這題的核心是理解如何使用 Stack 來追蹤未匹配的括號位置，利用索引差來算出有效括號長度。
雖然一開始有點抽象，但實作後會覺得非常直覺。
這個技巧也能延伸到括號匹配、語法檢查等實務場景，算是一個很實用的技能。