前言

今天我們來解一題挑戰難度的題目——Longest Valid Parentheses（最長有效括號）。

這道題目真的不簡單，因為它要求我們在一個由括號組成的字串中找出最長的有效括號子字串的長度。

有效的括號必須成對且按照正確順序配對好，這就有點像是在解一個括號迷宮！
雖然看起來很複雜，但我們可以用幾種不同的方法來解決，讓我們一起來逐步分析吧！

英文題目

Longest Valid Parentheses

難度：Hard

題目描述：

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses 

substring

.

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

範例 1：

輸入： s = "(()"

輸出： 2

解釋： 最長的有效括號子字串是 "()"。

範例 2：

輸入： s = ")()())"

輸出： 4

解釋： 最長的有效括號子字串是 "()()"。

範例 3：

輸入： s = ""

輸出： 0

尋找解決方案

這道題有多種解法，最直觀的可能是使用堆疊，但我們還可以用動態規劃或是雙指針的方式來解決。
下面我會重點介紹這三種方法，並挑選其中一種來詳細實作。

1. 方法 1：使用堆疊：

   • 堆疊可以用來追蹤左括號 '(' 的索引位置。
   • 當遇到右括號 ')' 時，我們嘗試彈出堆疊頂部的左括號，如果成功配對，則計算當前的有效長度。

2. 方法 2：動態規劃：

   • 定義一個 dp 陣列，dp[i] 表示以 s[i] 結尾的最長有效括號子字串的長度。
   • 當 s[i] 是 ')' 且能與之前的 '(' 配對時，更新 dp[i] 的值。

3. 方法 3：雙指針法（左掃描和右掃描）：

   • 使用兩個指針 left 和 right 分別計算左括號和右括號的數量。
   • 分別從左到右掃描一次，然後從右到左掃描一次，記錄最大有效長度。

詳細步驟

這裡我們選擇方法 1：使用堆疊來解題，因為它比較直觀且容易理解。

1. 初始化：

   • 使用一個堆疊 stack，並將 -1 入堆疊，表示初始位置。這有助於計算有效長度。

2. 遍歷字串：

   • 當遇到 '(' 時，將其索引 i 入堆疊。
   • 當遇到 ')' 時，從堆疊中彈出元素（代表配對的 '('）。如果堆疊不為空，計算當前有效括號的長度並更新最大值；如果堆疊為空，將當前索引 i 入堆疊，表示無法配對的起點。

3. 更新最大長度：

   • 每次遇到 ')' 並成功配對後，使用 i - stack.peek() 計算當前的有效括號長度，並更新最大長度。

思路

這道題要求我們找出最長的有效括號子字串的長度。
所謂有效括號，就是必須成對且順序正確的括號組合。例如，"()" 是有效的，但 ")(" 或 "(()" 就不是。
為了滿足這些條件，我們可以使用堆疊來追蹤括號的索引位置。

1. 堆疊的初始化：

   • 我們需要使用一個堆疊 stack 來存儲括號的索引。這樣在遍歷字串時，我們可以追蹤每一個 '(' 的位置。
   • 為了方便計算從字串起始處到當前位置的有效括號長度，我們先將 -1 放入堆疊。
   • -1 代表的是一個基準位置，當我們遇到一對完整的括號並計算長度時，可以用當前索引減去這個基準位置。

2. 遍歷字串並處理每個括號：

   • 我們從頭到尾遍歷字串 s，逐個處理其中的字符。
   • 當遇到左括號 '(' 時，將其索引入堆疊。這樣我們就記錄了這個左括號的位置。
   • 當遇到右括號 ')' 時，這意味著我們嘗試找到一個配對的左括號。我們從堆疊中彈出一個元素，表示這個左括號已經被匹配了。

3. 計算有效括號的長度：

   • 當我們遇到右括號並成功配對時，我們需要計算這段有效括號的長度。這可以通過當前右括號的索引減去堆疊頂部的索引來得到。
   • 具體來說，當我們彈出一個左括號後，堆疊中剩下的頂部元素 stack.peek() 代表的是未配對括號的最後位置。所以當前的有效長度為 i - stack.peek()，其中 i 是當前右括號的索引。
   • 每次計算出一個有效長度後，我們需要比較並更新 maxLength，用來存儲找到的最長有效括號長度。

4. 處理無法配對的右括號：

   • 如果當我們遇到右括號 ')' 時，堆疊是空的，這意味著這個右括號沒有可以配對的左括號。這時，我們需要將這個右括號的索引入堆疊。這樣做是因為，當下一次遇到有效的括號時，我們會從這個位置開始計算有效長度，而不是從更早的部分開始計算。

5. 最後結果：

   • 當我們遍歷完整個字串後，maxLength 就會存儲最長的有效括號子字串的長度。

實作

function longestValidParentheses(s: string): number {
    const stack: number[] = [-1]; // 初始位置為 -1，方便計算長度
    let maxLength = 0; // 記錄最大有效長度

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            // 遇到 '(' 時，將索引入堆疊
            stack.push(i);
        } else {
            // 遇到 ')' 時，彈出堆疊
            stack.pop();

            if (stack.length === 0) {
                // 如果堆疊為空，將當前索引入堆疊
                stack.push(i);
            } else {
                // 計算當前的有效括號長度
                maxLength = Math.max(maxLength, i - stack[stack.length - 1]);
            }
        }
    }

    return maxLength; // 返回最大有效長度
}

解題心法

1. 堆疊的使用：

   • 堆疊用來存儲未配對的左括號 '(' 的索引。當遇到右括號 ')' 時，我們嘗試將其與堆疊中的左括號配對。
   • 當堆疊為空時，說明無法與前面的左括號配對，此時我們將 ')' 的索引入堆疊，表示一個新的起點。

2. 有效長度的計算：

   • 每次成功配對後，我們使用當前索引 i 減去堆疊頂部的索引來計算有效長度，這樣可以確保配對的括號之間的區間長度是正確的。

3. 特殊情況處理：

   • 初始時將 -1 入堆疊是為了處理從最開始就有配對的情況，這樣我們可以正確地計算整個字串的有效長度。

為什麼這樣處理？

這種方法使用堆疊來追蹤括號配對的位置，可以在 O(n) 的時間內掃描整個字串，並在配對成功時計算出當前的有效長度。堆疊能夠方便地記錄未配對的括號位置，使我們能夠在掃描過程中即時計算最長的有效子字串長度。

本次要點：

• 堆疊：用來追蹤未配對的括號索引。
• 有效括號的長度計算：當成功配對時，使用當前索引減去堆疊頂部的索引來計算長度。
• 時間複雜度 O(n)：整個字串只需遍歷一次，並且堆疊操作的時間複雜度為 O(1)。

這道題是不是讓人覺得像是在解一個括號迷宮呢？
通過使用堆疊，我們可以一步步找到每個配對的括號，並且計算出最長的有效括號子字串。
希望你能在這道題中有所收穫，下次再一起挑戰更多有趣的題目吧！😊💪