AlgoPressAppearance
题目描述
https://leetcode.cn/problems/longest-valid-parentheses
给你一个只包含 '('和 ')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
- 0 <= s.length <= 3 * 10^4
- s[i] 为 '(' 或 ')'
思路：统计左右括号
先统计左括号，遇到右括号就开始累积统计总数 有问题： (()()(() 会统计成6个，但实际是4个
修正： 只有右括号等于左括号的时候，才统计个数，统计方法为 2 * right 如果 right > left 了，说明不合法的已经出现，不会从他开始构建有效括号，重新设置为0 不过这种算法会少统计一种情况即 (() ，此时反向遍历一次即可。
参考代码
csharp
public class Solution {
public int LongestValidParentheses(string s) {
int left = 0;
int right = 0;
int max = 0;
//从左往右统计
for(int i=0; i<s.Length; i++){
if(s[i] == '('){
left ++;
}
else{
right ++;
}
if(left == right){
max = Math.Max(max, 2 * right);
}
else if(right > left){
right = 0;
left = 0;
}
}
//从右往左统计 注意设置为零的条件
left = 0;
right = 0;
for(int i=s.Length -1 ; i>=0; i--){
if(s[i] == '('){
left ++;
}
else{
right ++;
}
if(left == right){
max = Math.Max(max, 2 * right);
}
else if(left > right){
right = 0;
left = 0;
}
}
return max;
}
}
思路，使用栈配合dp数组
左括号入栈，右括号出栈，出栈的时候判断计算最大长度 注意入栈的是索引号，这样出栈的时候，可以计算长度。
csharp
public class Solution{
public int LongestValidParentheses(string s){
Stack<int> stack = new Stack<int>();
int[] dp = new int[s.Length];
int max = 0;
for(int i=0; i<s.Length; i++){
if(s[i] == '('){
stack.Push(i);
}
else{ //出栈
if(stack.Count > 0){
int index = stack.Pop();
dp[i] = i - index + 1;
if(index > 0){
dp[i] += dp[index-1];
}
max = Math.Max(dp[i],max);
}
}
}
return max;
}
}