LeetCode32 最长有效括号
题目
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
0 <= s.length <= 3 * 10?
s[i] 为 '(' 或 ')'
方法
动态规划法
栈法
- 时间复杂度：O（n）
- 空间复杂度：O（n）
class Solution {
public int longestValidParentheses(String s) {
int max = 0;
Stack stack = new Stack<>();
stack.add(-1);
for(int i=0;i 双指针法
- 时间复杂度：O（n）
- 空间复杂度：O（1）
class Solution {
public int longestValidParentheses(String s) {
//正序遍历，找出（（）））右边多的合法子串
int l = 0,r = 0,max = 0;
int length = s.length();
for(int i=0;i=0;i--){
char c = s.charAt(i);
if(c=='('){
l++;
}else{
r++;
}
if(l==r){
max = Math.max(max,r*2);
}else if(l>r){
l = 0;
r = 0;
}
}
return max;
}
}