LeetCode第32题 : 最长有效括号

发布时间:2024年01月03日

题目介绍

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

示例 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);
    }
};

文章来源:https://blog.csdn.net/haokan123456789/article/details/135351710
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。