Skip to content

發布日期: March 23, 2024

最後更新: March 23, 2024

閱讀時間: ~ 5 min


LeetCode 32. Longest Valid Parentheses

題目

32. Longest Valid Parentheses

解題思路

括號判斷

要判斷括號是否有效,首先要判斷左右括號數量是否相等,一個簡單的方法是設一個計數器,遇到 '(' 字元時,將計數器加 1,遇到 ')' 字元時,將計數器減 1,最後判斷計數器是否為 0。但這種方法還缺少判斷括號是否有效的條件,例如 ")(" 字串,雖然左右括號數量相等,但括號不是有效的。

這裡我們先透過計數器來分析數字的變化,這種變化可以畫成折線圖,例如 ")()())" 字串,折線圖如下:

 1 |
 0 |\  /\  /\
-1 | \/  \/  \
-2 |          \
-3 |_____________

透過上述計數器原理,可以簡單推論出在折線圖上任意取兩個相同高度的點,此兩點間括號數量是相等的。

那要如何判斷括號是否有效呢?首先我們知道括號無效的情況就是 ')' 數量大於 '(' 數量,那假設折線圖上兩個相同高度的點,無效的情況就是兩點間的最低點比兩點高度還要低,例如上述例子中,")(" 字串,最低點為 -1,而兩個高度為 0 的點,最低點 -1 比高度 0 還要低,因此這個例子是無效的。

現在我們知道如何判斷括號是否有效了,接下來就是要找到折線圖上任兩個相同高度且符合有效括號的區段,並計算兩點間的距離,最後找出最長的距離就是答案了。

解法

既然要找兩點間的距離,那就需要一個陣列 (假設為 preX) 來記錄每個高度的位置,但這個陣列需要紀錄的位置是前一個同高度點的位置,而且要確保前一個點位到當前點位間的括號是有效的,這樣才能計算兩點間的距離。

首先我們來分析折線圖上的點,可以發現有兩種情況,我把這兩種情況區分為 遞增點位遞減點位遞增點位 是指前一個點位比當前點位高度還要低,反之就是 遞減點位

遞增點位

先來分析 遞增點位,由於前一個點位的高度比當前點位高度還要低,因此當前點位與前一個同高度點位間的括號是無效的,所以只要更新位置到 preX 即可。

遞減點位

接著分析 遞減點位,由於前一個點位的高度比當前點位高度還要高,因此當前點位與前一個同高度點位間的括號是有效的,這時就可以計算兩點間的距離,並更新答案。

最後有一個例外,在 遞減點位 的情況下,假設點位是處于 波谷 的位置,需要判斷前一個同高度點位是否存在,如果不存在,則需要更新位置到 preX

程式碼

cpp
class Solution {
public:
  int longestValidParentheses(string s) {
    int n = s.size();
    int res = 0;
    
    // 這裡的 preX 陣列是用來記錄前一個同高度點位的位置
    // 由於高度可能是負數,因此需要分配 2n+1 的空間 (正負最大值和 0)
    vector<int> preX((n << 1) + 1, -1);
    // zero 就是指在 preX 陣列中高度為 0 的 index
    int zero = n;
    // 記錄一開始高度為 0 的位置
    preX[zero] = 0;
    // preY 是前一個點位的高度, y 是當前點位的高度, 用來判斷遞增或遞減
    int preY = 0, y = 0;
    for (int i = 0; i < s.size(); ++i) {
      y += s[i] == '(' ? 1 : -1;
      // 計算當前點位的高度在 preX 陣列中的 index
      int _y = y + zero;

      if (preY < y) { // 遞增點位
        // 更新位置到 preX
        preX[_y] = i + 1;
      } else { // 遞減點位
        if (preX[_y] != -1) { // 前一個同高度點位存在
          // 計算兩點間的距離,並更新答案
          res = max(res, i + 1 - preX[_y]);
        } else if (i + 1 < s.size() && s[i + 1] == '(') { // 波谷點位
          // 更新位置到 preX
          preX[_y] = i + 1;
        }
      }

      preY = y;
    }

    return res;
  }
};

其他解法

這題我想的太複雜了,雖然時間複雜度跟其他方法是相同的,但空間複雜度是花費比較多的,而且程式碼和思路都比較複雜,有興趣的人可以去參考以下解法,分別是使用 StackTwo Pointers 的方式解題,這兩種方法比較直覺且容易理解。