题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

输入：s = ""
输出：0

解答 & 代码

动态规划 + 存储左括号下标的栈 leftIdxS:

动态规划数组 **dp**：dp[i] 代表以 s[i - 1] 结尾的最长有效括号长度
状态转移公式：设当前遍历到字符 s[i]，计算 dp[i + 1]
- 如果当前字符 s[i] == '('，则 '(' 的下标 i 入栈， **dp[i + 1] = 0**
- 如果当前字符 s[i] == ')'
  - 若栈 leftIdxS 为空，说明没有 '(' 和当前这个 ')' 匹配，因此 **dp[i + 1] = 0**
  - 否则，弹出栈顶存储的 '(' 的下标值记为 leftIdx，则当前配对的这对合法括号子串长度为 i - leftIdx + 1。但是这对括号子串前面可能还有合法的括号子串可以和当前的连起来，形成更长的有效括号子串，因此还要加上以 s[leftIdx - 1] 为结尾的最长有效括号长度。因此，d**p[i + 1] = dp[leftIdx] + i - leftIdx + 1**，并更新结果 result

初始化：dp[0] = 0

class Solution {
public:
  int longestValidParentheses(string s) {
      stack<int> leftIdxS;    // 栈，存储左括号的下标
      int result = 0;            // 结果：最长有效括号的长度
      // 动态规划数组 dp：dp[i] 代表以 s[i - 1] 结尾的最长有效括号长度
      vector<int> dp(s.size() + 1, 0);
      // 初始化
      dp[0] = 0;
      // 状态转移
      for(int i = 0; i < s.size(); ++i)
      {
          if(s[i] == '(')                // 1. 遇到左括号
          {
              leftIdxS.push(i);        // 在栈中存储左括号的索引
              dp[i + 1] = 0;            // 左括号不可能是有效括号子串的结尾
          }
          else                        // 2. 遇到右括号
          {
              if(leftIdxS.empty())    // 2.1 栈为空，即没有匹配的左括号
                  dp[i + 1] = 0;        // 则该右括号不是有效括号子串的结尾
              else                    // 2.2 栈不为空
              {
                  int leftIdx = leftIdxS.top();    // 记录配对的左括号的索引
                  leftIdxS.pop();                    // 弹出左括号
                  dp[i + 1] = dp[leftIdx] + i - leftIdx + 1;    // 状态转移
                  result = max(result, dp[i + 1]);    // 更新 result
              }
          }
      }
      return result;
  }
};

复杂度分析：设字符串长为 N

时间复杂度 O(N)：
空间复杂度 O(N)：

执行结果：

执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了70.04% 的用户
内存消耗：7.6 MB, 在所有 C++ 提交中击败了 6.49% 的用户

hot 100

[困难] 32. 最长有效括号

题目

解答 & 代码