專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

2025年1月7日，雷軍在個人社交媒體發布消息，小米集團召開2025年開年第一個大會，將連發6年的“百萬美金技術大獎”升級到了1000萬元人民幣。這是小米集團內部最高級別的技術獎項。今年獲得大獎的項目是“小米超級電機V8s”項目組。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第32題：最長有效括號。

問題描述

來源：LeetCode第32題

難度：困難

給你一個只包含 '(' 和 ')' 的字符串，找出最長有效（格式正確且連續）括號子串的長度。

示例1：

輸入：s = "(()" 輸出：2 解釋：最長有效括號子串是 "()"

示例2：

輸入：s = ")()())" 輸出：4 解釋：最長有效括號子串是 "()()"

• 0 <= s.length <= 3 * 10^4

• s[i] 為 '(' 或 ')'

問題分析

對于括號的匹配問題，我們最容易想到的就是使用棧stk，在開始的時候我們需要添加一個 標志位 ，這個 標志位表示當前位置及之前的字符不能再和后面的匹配了 。

在最開的時候添加標志位為 -1 ，比如前面 4 個字符如果都是有效的括號，那么第 4 個字符的下標是 3（下標是從 0 開始的），讓它減去標志位的值正好等于 4 。

然后我們遍歷字符串中的所有字符，如果遇到左括號就把它的下標 i 壓入到棧中。 如果遇到右括號，棧頂元素出棧，出棧之后如果棧不為空，那么當前右括號和出棧的括號是匹配的，以當前右括號為最右邊的有效括號長度就是 i - stk.peek() ，我們計算并保存最大值即可。

出棧之后如果棧為空，當前右括號是沒法匹配的，我們把他的下標 i 壓入到棧中，它就變成了標志位，我們畫個圖看下。

JAVA：

public int longestValidParentheses(String s) {     int max = 0;// 記錄最大長度     Stack
         
  stack =  new Stack<>(); // 棧     stack.push(- 1); // 先把-1壓棧      for ( int i =  0; i < s.length(); i++) {          if (s.charAt(i) ==  '(') {             stack.push(i); // 遇到左括號，下標壓棧         }  else {             stack.pop(); // 遇到右括號，棧頂元素先出棧。              if (stack.empty()) { // 如果棧為空，把這個右括號的下標壓棧。                 stack.push(i);             }  else { // 計算長度，保存最大值。                 max = Math.max(max, i - stack.peek());             }         }     }      return max; }

C++：

public:     int longestValidParentheses(string s) {         int ans = 0;// 記錄最大長度         stack

  stk;// 棧         stk.push(-1);// 先把-1壓棧         for (int i = 0; i < s.length(); i++) {             if (s[i] == '(') {                 stk.push(i);// 遇到左括號，下標壓棧             } else {                 stk.pop();// 遇到右括號，棧頂元素先出棧。                 if (stk.empty()) {// 如果棧為空，把這個右括號的下標壓棧。                     stk.push(i);                 } else {// 計算長度，保存最大值。                     ans = max(ans, i - stk.top());                 }             }         }         return ans;     }

C：

int longestValidParentheses(char *s) {     int ans = 0;// 記錄最大長度     int *stk = malloc(30000 * sizeof(int));// 棧     int index = 0;     stk[index++] = -1;// 先把-1壓棧     for (int i = 0; i < strlen(s); i++) {         if (s[i] == '(') {             stk[index++] = i;// 遇到左括號，下標壓棧         } else {             index--;// 遇到右括號，棧頂元素先出棧。             if (index == 0) {// 如果棧為空，把這個右括號的下標壓棧。                 stk[index++] = i;             } else {// 計算長度，保存最大值。                 ans = fmax(ans, i - stk[index - 1]);             }         }     }     return ans; }

Python：

def longestValidParentheses(self, s: str) -> int:     ans = 0  # 記錄最大長度     stk = [-1]  # 先把 -1 壓棧     for i, ch in enumerate(s):         if ch == '(':             stk.append(i)  # 遇到左括號，下標壓棧         else:             stk.pop()  # 遇到右括號，棧頂元素先出棧。             if not stk:  # 如果棧為空，把這個右括號的下標壓棧。                 stk.append(i)             else:  # 計算長度，保存最大值。                 ans = max(ans, i - stk[-1])     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。