32. Longest Valid Parentheses
[HARD]

题目描述

Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1
2
Input: s = ""
Output: 0

解题思路 - 1

DP，动态规划

我们用一个数组 dp[i] 来表示：

以第 i 个字符结尾的最长有效括号子串长度

举例：
s = “(()())”
dp[i] 记录了以位置 i 结尾（下标从 0 开始）时，最长有效括号的长度。

情况 1：s[i-1] == ‘(‘

说明当前字符和前一个字符组成了 “()”

情况 2：s[i-1] == ‘)’

那么看能不能把这个 ‘)’ 和之前的有效子串再往前的 ‘(‘ 配对。

代码 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:

    int longestValidParentheses(string s) {
        int n = s.length();

        if (n == 0) return 0;

        vector<int> dp(n,0);

        int maxLen = 0;

        for(int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLen = max(maxLen, dp[i]);
            }
        }

        return maxLen;
    }
};


解题思路 - 2

使用栈来解决这个问题。栈中存储的是未匹配的左括号的索引。

  1. 初始化一个栈和一个变量 max_len，用于记录最长有效括号的长度。
  2. 遍历字符串，对于每个字符：
    • 如果是左括号 ‘(‘，将其索引压入栈中。
    • 如果是右括号 ‘)’，检查栈是否为空：
      • 如果栈不为空，弹出栈顶元素，计算当前有效括号的长度，并更新 max_len。
      • 如果栈为空，将当前索引压入栈中。
  3. 返回 max_len。

代码 - 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestValidParentheses(s: str) -> int:
    stack = []
    max_len = 0
    
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            if stack:
                stack.pop()
                max_len = max(max_len, i - stack[-1] if stack else i + 1)
            else:
                stack.append(i)
    
    return max_len

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需要遍历字符串一次。
  • 空间复杂度：O(n)，在最坏情况下，栈中可能存储所有的左括号索引。

示例

1
2
s = "(()"
print(longestValidParentheses(s))  # 输出 2

解释

  • 对于输入 “(()”，最长的有效括号子串是 “()”，长度为 2。

注意事项

  • 确保输入字符串只包含 ‘(‘ 和 ‘)’。
  • 如果输入字符串为空，返回 0。