HHot 100C++ 图解

32. 最长有效括号

困难 动态规划(一维) 3 帧动画 在力扣上做

一句话套路栈底存最后一个破坏位 / 也可区间 DP

题目描述

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

左右括号匹配,即每个左括号都有对应的右括号将其闭合的字符串是格式正确的,比如 "(()())"。

 

示例 1:

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

示例 2:

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

示例 3:

输入:s = ""
输出:0

 

提示:

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ')'

思路

时间O(n)

思路

思路(栈,最好记):栈底始终存「最后一个破坏合法性的位置」,初始压 -1。

遇 '(' 压下标;遇 ')' 先弹一个:

  • · 弹完栈空 -> 这个 ')' 成为新的分隔符,压下它的下标;
  • · 否则栈顶就是当前匹配段的「左边界前一位」,长度 = i - 栈顶。

思路(DP)

dp[i] = 以 i 结尾的最长有效长度。

s[i]==')' 时看 s[i-1]:是 '(' 则 dp[i]=dp[i-2]+2;

是 ')' 则看 s[i-dp[i-1]-1] 是否为 '(',是则再拼上前面的 dp[i-dp[i-1]-2]。

思路(双指针)

左右各扫一遍,open==close 时更新、close>open 时归零 ——为什么必须扫两遍?因为 "(()" 只有左到右扫会漏掉。

图解

) 0 ( 1 ) 2 ( 3 ) 4 ) 5 L R
有效段 ()() 长度 4(下标 1..4)。思路:存下标做栈,用「上一个不匹配位置」当左界,每段长度 = i - 栈顶。

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/15_dp.cpp39 行
namespace lc0032 {
class Solution {
 public:
  static int longestValidParentheses(const string& s) {
    int ans = 0;
    vector<int> st{
        -1};  // 栈底:最后一个「无法匹配」的位置(哨兵)
    for (int i = 0; i < (int)s.size(); ++i) {
      if (s[i] == '(') {
        st.push_back(i);
      } else {
        st.pop_back();
        if (st.empty())
          st.push_back(i);  // 多余右括号,成为新分隔符
        else
          ans = max(ans, i - st.back());
      }
    }
    return ans;
  }

  static int longestValidParenthesesDP(const string& s) {
    const int n = (int)s.size();
    vector<int> dp(n, 0);  // dp[i]:以 s[i] 结尾的最长有效括号长度
    int ans = 0;
    for (int i = 1; i < n; ++i) {
      if (s[i] != ')') continue;
      if (s[i - 1] == '(') {
        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
      } else {
        int j = i - dp[i - 1] - 1;  // 与 s[i] 配对的候选左括号位置
        if (j >= 0 && s[j] == '(') dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
      }
      ans = max(ans, dp[i]);
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q32_longest_valid_parentheses12 行
lc0032::Solution s;
CHECK_EQ(s.longestValidParentheses(")()())"), 4);
CHECK_EQ(s.longestValidParenthesesDP(")()())"), 4);
CHECK_EQ(s.longestValidParentheses(""), 0);
CHECK_EQ(s.longestValidParentheses("()"), 2);
CHECK_EQ(s.longestValidParentheses("(()"), 2);
CHECK_EQ(s.longestValidParentheses("()(()"), 2);
CHECK_EQ(s.longestValidParentheses("()(())"), 6);
CHECK_EQ(s.longestValidParenthesesDP("()(())"), 6);
CHECK_EQ(s.longestValidParentheses("(()(()"), 2);   // 两段被夹住
CHECK_EQ(s.longestValidParenthesesDP("())((())"), 4);
CHECK_EQ(s.longestValidParentheses("())((())"), 4);

↑↓ 选择↵ 打开/ 随时唤起