LeetCode第32题 : 最长有效括号

题目介绍

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

示例 1：

输入：s = "(()"

输出：2

解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"

输出：4

解释：最长有效括号子串是 "()()"

使用栈解决

这题让求的是最长有效括号长度，一个有效的括号一定是满足下面两个条件：

• 左括号和右括号的数量一定是相等的。

• 在有效括号的任何位置左括号的数量一定是大于等于右括号的数量。

根据这两个特性我们可以使用栈来解决，栈中存放的是字符的下标，解决思路就是：

• 如果遇到左括号我们就把他的下标压栈。

• 如果遇到右括号，栈顶元素出栈，如果栈不为空说明出栈的元素和这个右括号匹配，我们需要计算他们的长度，保留最大值即可。如果栈为空，直接把这个右括号所在的下标压栈。

这里要注意如果给定的字符串从一开始就是有效的括号，比如"()())"前4个符号是有效的括号，我们是没法计算他的长度的，因为第一个字符前面是没有字符的，所以我们默认第一个字符前面的下标是-1，然后把他压栈，我们以示例2为例画个图来看下。

最后看下代码：

class Solution {
public:
    int flags[20000];
    int longestValidParentheses(string s) {
        int n = s.size();
        stack<int> stk;//存储的是下标
        for(int i = 0; i < n; ++i){
            if(s[i] == '(') 
                stk.push(i);//左括号push
            else{
                if(stk.empty())   
                    flags[i] = 1;
                else    
                    stk.pop();
            }
        }
        
        while(!stk.empty()){
            flags[stk.top()] = 1;
            stk.pop();
        }
        
        int res = 0, len = 0;
        for(int i = 0; i < n; ++i){
            if(flags[i] == 0)   
                ++len;
            else{
                res = max(res, len);//长度更新
                len = 0;
            }
        }
        return max(res, len);//可能需要考虑最后的位
    }
};

动态规划

再来看下动态规划该怎么解决，我们用dp[i]表示以是s[i]为结尾的最长有效括号长度，如果要计算dp[i]就会有下面几种情况：

• 第i个字符是左括号"("，那么以他结尾的是构不成有效括号的，所以dp[i]=0;

• 第i个字符是右括号")"，那么以他结尾的是有可能构成有效括号的，所以还需要继续判断：

1. 这里我们需要判断他前面的也就是第i-1个字符，如果第i-1个字符是左括号"("，类似于……()，那么最长有效括号就是第i-2个字符之前构成的最长有效括号+2，也就是dp[i]=dp[i-2]+2。

2. 如果第i-1个字符也是右括号")"，类似于……((……))，如下图所示，我们还需要判断第i -1- dp[i - 1]个字符是否是左括号"(",如果是"("，那么递推公式是dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]，这里dp[i - dp[i - 1] - 2]是第一个省略号构成的有效括号长度，这个不要忘了。

最后看下代码：

class Solution {
public:
    int dp[20000];
    int longestValidParentheses(string s) {
        int n = s.size();
        for(int i = 1; i < n; ++i){
            if(s[i] == ')'){//合法的子串一定以右括号结尾
                if(s[i-1] == '(')  
                    dp[i+1] = dp[i-1] + 2; 
                else if(i-1-dp[i] >= 0 && s[i-1-dp[i]] == '(')  
                    dp[i+1] = dp[i] + dp[i-1-dp[i]] + 2;
            } 
        }
        return *max_element(dp+1, dp+n+1);
    }
};