LeetCode hot 100—最长有效括号
题目
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"示例 3：
输入：s = "" 输出：0
分析
可以使用动态规划的方法来解决这个问题。我们定义一个数组 dp，其中 dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度。
动态规划
代码解释
初始化：n 为字符串 s 的长度。dp 数组初始化为 0，长度为 n。maxLength 用于记录最长有效括号子串的长度，初始化为 0。
动态规划过程：
- 遍历字符串
s，从第二个字符开始（因为第一个字符不可能组成有效括号子串）。 - 如果当前字符是
)：- 情况一：如果前一个字符是
(，则可以与前一个字符组成一对有效括号。此时dp[i]等于dp[i - 2]（如果i >= 2）加上 2。 - 情况二：如果前一个字符也是
)，则需要检查更前面的字符是否能组成有效括号。如果i - dp[i - 1] > 0且s[i - dp[i - 1] - 1] == '('，则dp[i]等于dp[i - 1]加上dp[i - dp[i - 1] - 2]（如果i - dp[i - 1] >= 2）再加上 2。
- 情况一：如果前一个字符是
- 更新
maxLength为dp[i]和maxLength中的较大值。
返回结果：
- 最后返回
maxLength，即最长有效括号子串的长度。
时间复杂度：O()，
是字符串的长度
空间复杂度：O()
class Solution {
public:int longestValidParentheses(string s) {int n = s.length();if (n == 0) return 0;// dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度vector<int> dp(n, 0);int maxLength = 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;}maxLength = max(maxLength, dp[i]);}}return maxLength;}
};