[LeetCode] 32.最长有效括号

Richard

2024 年 05 月 01 日

93 次浏览

暂无评论

2449字数

LeetCode

> https://leetcode.cn/problems/longest-valid-parentheses/description/

### DP

对于每个 `)` ，设其位置为 $i$ ，有以下两种情况：

- 如果位置 $i - 1$ 的字符是 `(` ，则表明这两个括号已经是格式正确的括号对了，此时只需要用 $i - 2$ 的最大有效长度 `dp[i - 2]` 加上 $2$ 就是该位置最大的有效长度。
- 如果 `i - dp[i - 1] - 1` 存在且为 `(` ，则表明这两个括号以及中间包含的括号都是符合要求的括号对，长度为 `dp[i - 1] + 2` 。由于往前扩展了位置，因此可能和前面的有效括号对相接，所以应该再加上一个 `dp[i - dp[i - 1] - 2]` 。

```c++
class Solution {
public:
    int longestValidParentheses(std::string s) {
        const int len = s.length();

int longest = 0;
        std::vector<int> validLength(len);
        for (int i = 1; i < len; ++i) {
            if (s[i] == '(')
                continue;

if (s[i - 1] == '(') {
                validLength[i] = (i >= 2 ? validLength[i - 2] : 0) + 2;
            } else if (i - validLength[i - 1] > 0 && s[i - validLength[i - 1] - 1] == '(') {
                validLength[i] = validLength[i - 1] + 2 + 
                        (i - validLength[i - 1] >= 2 ? validLength[i - validLength[i - 1] - 2] : 0);
            }
          
            if (validLength[i] > longest)
                longest = validLength[i];
        }
      
        return longest;
    }
};
```

- 时间复杂度：$O(n)$ 。
- 空间复杂度：$O(n)$ 。

### 贪心

利用两个计数器 `left` 和 `right` ，从左到右遍历字符串。遇到 `(` 就增加 `left` 计数器，遇到 `)` 就增加 `right` 计数器。当 `left == right` 的时候就表明此时括号是完全匹配的，此时计算有效字符串的长度并记录最长的长度。当 `left < right` 时，说明此时括号对已经不合法了，因此把 `left` 和 `right` 置零，重新开始计数。

但这么做有个问题，对于 `(()` 这种左括号数多于右括号数的情况，这种贪心就没法解决了。这时候只需要用相同的方法从右往左遍历一次即可解决，注意条件也要反过来即可。

```c++
class Solution {
public:
    int longestValidParentheses(std::string s) {
        const int len = s.length();

int left = 0, right = 0, res = 0;
        for (int i = 0; i < len; ++i) {
            if (s[i] == '(')
                ++left;
            else
                ++right;

if (left < right)
                left = right = 0;
            else if (left == right)
                res = std::max(res, left);
        }      
      
        left = 0, right = 0;
        for (int i = len - 1; i >= 0; --i) {
            if (s[i] == '(')
                ++left;
            else
                ++right;

if (left > right)
                left = right = 0;
            else if (left == right)
                res = std::max(res, left);
        }
      
        return res * 2;
    }
};
```

- 时间复杂度：$O(n)$ ，正反遍历两边字符串即可。
- 空间复杂度：$O(1)$ 。

最后修改：2024 年 05 月 12 日