题目来源
题目详情
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入： s = "(()"
输出： 2
解释： 最长有效括号子串是 "()"
示例 2：
输入： s = ")()())"
输出： 4
解释： 最长有效括号子串是 "()()"
示例 3：
输入： s = ""
输出： 0
提示：
0 <= s.length <= 3 * 104-
s[i]为'('或')'
题解分析
解法一：动态规划
- 本题要求解最长有效括号子串长度，碰到子串，最长等描述词语就能想到应该使用动态规划来求解。
- 本题的难点就在于状态转移方程的定义，这部分是比较难分析的，因为这里涉及到两种符号：即左括号和右括号。而左右括号之间会相互影响。
- 我们可以定义dp[i]表示以i结尾的最长有效符号子串的长度。接下来分析可能出现的情况。
- 首先需要说明的是，当前符号为"("时，其实不用考虑，因为这种情况一定不能构造出比前面的子串更长的有效括号子串。所以，我们只考虑当前符号为")"的情况。
- 第一种情况是，当前符号的前一个符号为"("。也就是说，字符串的形式为："...()"。这里很容易得到：\(dp[i] = dp[i-2] + 2\);
- 第二种情况是：当前符号的前一个符号为")"。也就是说，字符串的形式为："...((...))"。这里需要判断，当第\(i-dp[i-1]-1\)个字符为"("时，可以得到状态转移方程：\(dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2\)。
- 综上，我们可以定义一个最大值记录量max，用来记录最长有效括号子串的长度。
class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
int[] dp = new int[n];// dp[i]表示以i结尾的子串的最长有效括号子串的长度
int max = 0;
for(int i=1; i<n; i++){
char ch = s.charAt(i);
if(ch == ')'){// 只有当结尾符号为右括号时才有可能构造出有效括号子串，否则等价于前面碰到左括号的情况
if(s.charAt(i - 1) == '('){
// "...()"的情况
dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
}else if(i - dp[i-1] >= 1 && s.charAt(i-dp[i-1]-1) == '('){
// "...((...))"的情况
dp[i] = dp[i-1] + 2 + ((i - dp[i-1] >= 2) ? dp[i-dp[i-1]-2] : 0);
}
}
max = Math.max(max, dp[i]);
}
return max;// 注意，这里不能返回dp[n-1]，因为这里不能保证以n-1结尾的符号一定有满足连续的最长有效括号子串
}
}
解法二：栈
- 使用栈的解法比较复杂，也比较难以理解，这里考了一些思维。
- 通过栈可以维护【字符串中最后一个未匹配的右括号的下标位置】。
- 具体的可以参考官方题解。
class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
int max = 0;
Deque<Integer> sta = new LinkedList<>();// 栈用来存放字符串中最后的没有被匹配的右括号的位置
sta.push(-1);// 为了保持统一，放入-1表示最后一个未被匹配的右括号位置为-1
for(int i=0; i<n; i++){
char ch = s.charAt(i);
if(ch == '('){
sta.push(i);// 碰到左括号直接入栈
}else{
sta.pop();// 碰到右括号时出栈栈顶元素，假设已经配对了
if(sta.isEmpty()){
sta.push(i);// 右括号和栈顶元素没有配对成功
}else{
max = Math.max(max, i - sta.peek());
}
}
}
return max;
}
}