最长有效括号 - LeetCode 热题 90
大家好！我是曾续缘🤪
今天是《LeetCode 热题 100》系列
发车第 90 天
动态规划第 10 题
❤️点赞 👍 收藏 ⭐再看，养成习惯
最长有效括号 给你一个只包含
'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。难度：💝💝💝示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"示例 3：
输入：s = "" 输出：0提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
解题方法
- 使用一个数组
f记录以每个字符结尾的最长有效括号子串的长度。 - 遍历字符串
s，对于每个位置i，我们尝试更新f[i]。 - 如果
s[i]是')'，我们需要考虑两个情况：- 如果
s[i - 1]是'('，那么当前的')'可以和i - 1位置的'('配对，这时候我们需要查看i - 2位置的有效括号长度（如果i - 2在数组范围内），然后加上当前的2（因为包含当前的')'）。 - 如果
i - f[i - 1] > 0并且s[i - f[i - 1] - 1]是'('，那么当前的')'可以和i - f[i - 1] - 1位置的'('配对，这时候我们需要更新f[i]为f[i - 1] + 2 + (i - f[i - 1] - 2 >= 0 ? f[i - f[i - 1] - 2] : 0)。
- 如果
Code
class Solution {public int longestValidParentheses(String s) {int n = s.length();int[] f = new int[n];for(int i = 1; i < n; i++){if(s.charAt(i) == ')'){if(s.charAt(i - 1) == '('){f[i] = (i >= 2 ? f[i - 2] : 0) + 2;}else if(i - f[i - 1] > 0 && s.charAt(i - f[i - 1] - 1) == '('){f[i] = f[i - 1] + ((i - f[i - 1]) >= 2 ? f[i - f[i - 1] - 2] : 0) + 2;}}}int ans = 0;for(int x : f){ans = Math.max(ans, x);}return ans;}
}