前言

嘿嘿～我們又回來啦！延續上次的 Longest Valid Parentheses 題目，這次我們要換個方式來解決。還記得上次我們用了動態規劃法嗎？

今天我們要來介紹一個超高效的解法——雙指針法！這個方法不用額外空間，只靠兩個小計數器就能快速找到最長有效括號的長度～

是不是很期待？接下來我們來介紹 方法 3：雙指針法。

雙指針法透過一次從左到右、一個從右到左的掃描，來計算最長的有效括號長度。這個方法的時間複雜度依然是 O(n)，但不需要額外的空間，僅需兩個計數器，非常輕量級。

方法 3：雙指針法

思路解析

這個方法基於這樣一個觀察：在一個有效的括號序列中，左括號的數量必須等於右括號的數量，並且在任何時刻，右括號的數量不能超過左括號的數量。這為我們提供了使用雙指針掃描的可能性。

具體來說，我們會進行兩次掃描：

1. 第一次從左到右掃描：在這個過程中，我們用兩個計數器 left 和 right 來計數左括號 ( 和右括號 ) 的數量。如果在某個時刻 left == right，那麼我們就找到了一個有效的括號序列，並記錄下它的長度。如果 right 超過了 left，說明這個時刻無法再形成有效序列，我們就重置計數器。

2. 第二次從右到左掃描：同樣地，我們再次使用 left 和 right 進行計數，不過這次我們從右到左掃描字串，因為在有效的括號序列中，左括號的數量也不能超過右括號。

通過這兩次掃描，我們可以保證無論括號的排列方式如何，都能夠找出最長的有效子字串。

詳細步驟

1. 初始化計數器：

   • 我們初始化兩個計數器 left 和 right 來計數括號。
   • 初始化 maxLength 來記錄最長有效括號的長度。

2. 第一次從左到右的掃描：

   • 我們遍歷字串，當遇到左括號 ( 時，增加 left 計數；遇到右括號 ) 時，增加 right 計數。
   • 當 left == right 時，說明找到了一個有效的括號序列，更新 maxLength。
   • 如果 right > left，說明右括號過多，無法再形成有效括號，重置計數器。

3. 第二次從右到左的掃描：

   • 同樣地，這次從右往左掃描字串，並在每次遇到左括號或右括號時更新計數器。
   • 當 left == right 時，同樣更新 maxLength。
   • 如果 left > right，說明左括號過多，無法形成有效括號，重置計數器。

實作

function longestValidParentheses(s: string): number {
    let left = 0, right = 0, maxLength = 0;

    // 從左到右掃描
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            left++;
        } else {
            right++;
        }

        if (left === right) {
            maxLength = Math.max(maxLength, 2 * right); // 有效括號長度是 2 * right
        } else if (right > left) {
            left = right = 0; // 重置計數器
        }
    }

    // 從右到左掃描
    left = right = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === ')') {
            right++;
        } else {
            left++;
        }

        if (left === right) {
            maxLength = Math.max(maxLength, 2 * left); // 有效括號長度是 2 * left
        } else if (left > right) {
            left = right = 0; // 重置計數器
        }
    }

    return maxLength;
}

解題心法

1. 雙指針的意義：

   • 通過左右兩次掃描，我們確保了在整個字串中，不論括號的排列方式如何，都能夠找到最長的有效括號序列。
   • 左到右的掃描確保了右括號不會多於左括號，而右到左的掃描則確保了左括號不會多於右括號。

2. 時間與空間複雜度：

   • 時間複雜度：O(n)，因為我們進行了兩次線性掃描。
   • 空間複雜度：O(1)，我們只使用了常數級別的空間來儲存計數器。

方法比較

現在我們已經介紹了三種解法，讓我們來簡單比較一下這三種方法：

1. 方法 1：堆疊法：

   • 優點：直觀，易於理解。適合剛接觸這類問題的人。
   • 缺點：需要額外的 O(n) 空間來存儲堆疊，效率稍低。

2. 方法 2：動態規劃法：

   • 優點：通過 dp 陣列有效追蹤每個位置的解，適合分析較複雜的括號結構。
   • 缺點：仍然需要 O(n) 的空間來存儲 dp 陣列。

3. 方法 3：雙指針法：

   • 優點：時間和空間複雜度均為 O(n) 和 O(1)，最省空間的解法。
   • 缺點：不如前兩種方法直觀，理解上需要更多邏輯思考。

小結

今天我們學到了雙指針法這種高效的解法！通過兩次掃描字串，我們能夠在 O(n) 的時間內找到最長的有效括號長度，而且只需要常數空間，非常適合大數據量的處理。這種方法雖然不如堆疊法和動態規劃法直觀，但在追求效率時是一個很好的選擇。

希望這篇文章能幫助你掌握這種高效的解法！下次我們再來比較這三種方法的具體應用場景吧～ 💪