力扣32:最长有效括号

题目

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。

思路

方法一：栈
括号类的题目我们首先想到的是应该是用栈来做，这道题也不例外。对于这种有关最值的问题我们先不要管最值，先思考我们如何得到有效括号子串的长度。其实我们仔细想一想子串的长度不就是最后一个有效的右括号的下标减去最后一个无效的右括号下标吗，例如这个字符串")(())()“我们来观察一下有效子串的长度应该如何更新，不就是后面的右括号下标减去第一个右括号的下标吗。所以我们只要保证栈底里永远存着一个最后一个无效的右括号下标即可在我们每次匹配完成后就可以用当前下标去减去这个下标就可以得到有效括号子串的长度了。
所有我们还是正常对左右括号进行处理，遇到左括号进行push，遇到右括号进行pop同时更新最长子串的值。为了保证我们pop时栈不为空也就是如果字符串开头不是左括号而是右括号例如”())“这样，我们先对栈push一个-1。
方法二：动态规划
对于这道题我们是否还有其他的思路，当我们遇到一个有效子串也就是一个左括号一个右括号，那么新的有效长度不就是在原来的基础上进行+2吗。所以我们是否可以设置一个数组来存储以当前位置为结尾的有效子串长度。
那么对于左括号和右括号来说数组的值分别是多少呢，对于左括号来说如果以一个左括号为结尾那么有效子串长度毫无疑问就是0，而对于一个右括号来说子串的长度就需要进行讨论了。所以我们在创建数组时可以先将其全部置为0然后只对遇到右括号时再进行剩下的处理。那么遇到右括号一共不就两种情况吗前一个位置是左括号和前一个位置不是左括号，如果前一个位置是左括号那么不就匹配成功了我们就可以在原本的基础上对子串长度加2即可。关键是如果前一个位置不是左括号呢，这时候我们就需要再做一个判断也就是在去除那些有效子串后的位置是不是左括号例如这种情况”()(()())",当我们遇到最后一个右括号时我们发现它也是匹配成功的只是匹配的远了点所以我们需要判断在去除了前面的有效子串后的前一个位置是不是左括号，如果是我们就可以在数组的再前一个位置的基础上进行+2。
一样的我们发现数组的每一个位置都是答案所以这也是动态规划思想。

代码

方法一：栈

class Solution {
public:int longestValidParentheses(string s) {stack<int> st;st.push(-1);int res = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {// 如果遇到左括号就插入栈中st.push(i);} else {// 如果是右括号// 先对栈进行pop，因为我们提前插入了一个-1所以栈不可能为空st.pop();// 如果在pop后栈为空了说明从这个位置开始要重新计算长度了if (st.empty()) {st.push(i);} else {res = max(res, i - st.top());}}}return res;}
};

方法二：动态规划

class Solution {
public:int longestValidParentheses(string s) {int res = 0;int n = s.size();// 使用数组存储以当前位置为结尾的符合条件的最长子串的长度vector<int> dp(n, 0);for (int i = 1; i < n; i++) {// 如果为左括号则不用管因为以左括号为结尾肯定不符合条件if (s[i] == ')') {// 有两种情况，i-1是左括号或者右括号if (s[i - 1] == '(') {// 如果是左括号则说明括号匹配上了dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;}// 如果为右括号// 还需要判断去除前面的有效括号后的那位字符是不是左括号// 如果是就匹配上了else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {dp[i] = dp[i - 1] +(i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}res = max(res, dp[i]);}}return res;}
};