【力扣LeetCode】32 最长有效括号

本文主要是介绍【力扣LeetCode】32 最长有效括号，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述（难度难）

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

链接

https://leetcode-cn.com/problems/longest-valid-parentheses/

思路

1、最暴力的方法，对每个子串检验是否满足要求，对子串检测参考第20题：
https://leetcode-cn.com/problems/valid-parentheses/
解答见另一篇博客：
https://blog.csdn.net/u013095333/article/details/90714399
这样做时间上肯定过不了。

2、动态规划，用dp[i][j]表示从i到j的括号左括号比右括号多的数量，如果某一时刻为负数，即右括号比左括号多，则以i开头，长度大于j的子串均不可能有效。不过这个做法，可以过227/230个用例，对于一个字符串长度达到12477超过题目限制内存。
这里还有一个小细节，在分配dp数组的空间时，由于数组特别大，如果直接以局部变量的形式在栈上面分配，则编译无法通过，（使用变量给数组，则运行会失败）。需要在堆上分配二维数组。
在堆上分配二维数组参考：

https://www.cnblogs.com/yyxt/p/4268304.html
https://blog.csdn.net/lavorange/article/details/42879605

对于本题，leetcode内存限制，即使在堆上分配，程序运行没有问题，但是却过不了。

3、动态规划，改进dp，或者使用栈？见：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/
动态规划较为复杂一点
使用栈比较好理解一些

4、我们利用两个计数器 left 和 right 。首先，我们从左到右遍历字符串，对于遇到的每个 (，我们增加 left 计算器，对于遇到的每个 ) ，我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。如果 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。

接下来，我们从右到左做一遍类似的工作。
非常高效，算法动画图见：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/

代码

第2种情况的代码，leetcode过不了：

class Solution {
public:int longestValidParentheses(string s) {int slen = s.length();if(slen == 0){return 0;}// 在堆上分配空间，会超过内存限制// 直接在栈上分配空间，会导致编译错误，栈上分配不了这么大的空间 // int dp[slen][slen];int **dp = NULL;dp = new int*[slen];for(int i = 0; i < slen; i++){dp[i] = new int[slen];}for(int i = 0; i < slen; i++){for(int j = 0; j < slen; j++){dp[i][j] = -2;}}for(int i = 0; i < slen; i++){if(s[i] == '('){dp[i][i] = 1;}if(s[i] == ')'){dp[i][i] = -1;}}for(int i = 1; i < slen; i++){ // 距离 for(int j = 0; j + i < slen; j++){if(dp[j][j+i-1] >= 0){if(s[j+i] == '('){dp[j][j+i] = dp[j][j+i-1] + 1;}if(s[j+i] == ')'){dp[j][j+i] = dp[j][j+i-1] - 1;}}}}int ans = 0;for(int i = 0; i < slen; i++){for(int j = i; j < slen; j++){// cout << i << " " << j << " " << dp[i][j] << endl;if(dp[i][j] == 0){if(ans < j-i){ans = j-i+1;}}}}return ans;}
};

第4种方案代码：

class Solution {
public:int longestValidParentheses(string s) {int slen = s.length();if(slen == 0){return 0;}int left = 0;int right = 0;int ans = 0;int ansTemp = 0;for(int i = 0; i < s.length(); i++){if(s[i] == '('){left++;}if(s[i] == ')'){right++;if(right > left){right = 0;left = 0;ansTemp = 0;continue;}}ansTemp++;if(left == right){if(ans < ansTemp){ans = ansTemp;}}}ansTemp = 0;left = 0;right = 0;for(int i = s.length() - 1; i >= 0; i--){if(s[i] == ')'){right++;}if(s[i] == '('){left++;if(right < left){right = 0;left = 0;ansTemp = 0;continue;}}ansTemp++;if(left == right){if(ans < ansTemp){ans = ansTemp;}}}return ans;}
};