最长的括号子串_

JacobGo！

第二次做这道题了，更新一下解法吧

解法一是使用堆栈，在leeocode上提交了以后已经提示超时了，所以不推荐这种解法

我记得今年招银？校招有一道类似的题，我当时用的是堆栈，通过率并不高。

直接看代码吧：分别是用堆栈和动态规划求解

/*
 * 非动态规划，有时候会超时
 */
public int longestValidParentheses(String s) {
    if (s == null || s.length() < 1)
        return 0;
    Stack<Integer> stack = new Stack<Integer>();
    int max = 0, left = -1;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(')
            stack.push(i);
        else {
            if (!stack.isEmpty()) {
                stack.pop();
                if (!stack.isEmpty())
                    max = Math.max(max, i - stack.peek());
                else
                    max = Math.max(max, i - left);
            } else
                left = i;
        }
    }
    return max;
}

	

// Your runtime beats 92.48 % of java submissions.
public int longestValidParentheses2(String s) {
    if (s == null || s.length() == 0)
        return 0;
    int[] dp = new int[s.length()];
    int ans = 0;
    for (int i = 1; i < s.length(); i++) {
        // 如果是'('直接跳过，默认为0
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(')
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            // 说明s.charAt(i - 1)==')'
            else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
                // 因为加了一个左括号和一个右括号，所以是加2
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

编辑于 2018-01-06 20:55:00 回复(3)

sky_

//维护一个栈，里面保存'('的下标，每次进入一个')'时，栈弹出，ans更新为当前扫描的下标
//与栈顶元素之间的距离(因为中间可能有些括号已经被消掉了)，因为栈可能为空，所以需要
//记录下起始记录点last。
class Solution {
public:
    int longestValidParentheses(string s) {
        int ans=0,last=-1;
        stack<int> st;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') st.push(i);
            else{
                 if(!st.size()) last=i;
                 else{
                    st.pop();
                    if(st.size()) ans=max(ans,i-st.top());
                    else ans=max(ans,i-last);
                 }
            }
        }
        return ans;
    }
};

发表于 2017-08-05 10:58:14 回复(2)

老北京2018

发表于 2019-05-11 16:03:03 回复(0)

大灰兔

主要难点在于怎么保存同级之前的匹配，比如()()中的前面的()，可以采用prev：

class Solution(object):
    def longestValidParentheses(self, s):
        res = 0
        stack = []
        prev = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i - prev)
                prev = 0
            else:
                if len(stack) > 0:
                    prev = i - stack.pop() + 1
                    res = max(res, prev)
                else:
                    prev = 0
        return res

发表于 2017-10-07 23:37:45 回复(0)

猿辅导内推官

public static int longestValidParentheses(String s) {
    if (s.length() == 0) return 0;
    int left = 0;
    int right = 0;
    int maxLength = 0;
    //从左边遍历，左括号则left加1，有括号则right加1
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '('){
            left++;
        }else {
            right++;
        }
        //left和right相等则最大值为left，
        if (left == right){
            maxLength = Math.max(maxLength,left);
        }else if(left < right){ //如果left小于了right则证明不连续了，将left和right置位0
            left = 0;
            right = 0;
        }
    }
    left = 0;
    right = 0;
    //同样的道理，从右往左倒序遍历一次，左括号则left加1，有括号则right加1
    for (int i = s.length()-1; i >= 0; i--) {
        if (s.charAt(i) == '('){
            left++;
        }else {
            right++;
        }
        //left和right相等则最大值为left，
        if (left == right){
            maxLength = Math.max(maxLength,left);
        }else if(left > right){//如果left大于了right则证明不连续了，将left和right置位0
            left = 0;
            right = 0;
        }
    }
    return maxLength*2;
}

发表于 2021-04-08 16:30:32 回复(0)

C/C++

chenlongxi

这题关键的点应该是保存index，而不是保存字符。将index保存在栈中，然后匹配的index会出栈，剩下的就是不能匹配的index。其中有两个细节需要注意，就是栈底应该多个0，栈顶要多个s.size()。原因是对于“（）”这种情况。

int longestValidParentheses(string s)
{
    stack<int> sta; int count = 0, max_len = 0; bool fflag = true;
    for (int i = 0; i < s.size(); ++i)
    {
        if (!sta.empty() && s[i] == ')' && s[sta.top()] == '(')
        {
            sta.pop();
        }
        else
        {
            sta.push(i);
        }
    }
    if (sta.empty()) return s.size();
    count = s.size();
    while (!sta.empty())
    {
        count = count - sta.top() - 1;
        max_len = max(count, max_len);
        count = sta.top();
        sta.pop();
    }
    max_len = max(count, max_len);
    return max_len;
}

编辑于 2018-03-27 22:02:52 回复(1)

Java

李橙子

我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以 ‘)’ 结尾，因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值

从前往后遍历字符串求解 dp 值，我们每两个字符检查一次

1、s[i] = ')' 且 s[i-1] = '('，表示字符串形如 ‘......()’，则可推出：

dp[i] = dp[i-2] + 2

以进行这样的转移，是因为结束部分的 "()" 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2

2、s[i] = ')' 且 s[i-1] = ')'，表示字符串形如 ‘......))’，则可推出：

如果s[i - dp[i-1] - 1] = '('，则

dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2

考虑如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 subs），对于最后一个‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 subs的前面）。因此，如果子字符串 subs 的前面恰好是 ‘(’ ，那么我们就用 2 加上 subs 的长度（dp[i−1]）去更新 dp[i]。同时，也会把有效子串 “(subs)” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]。

最后的答案即为 dp 数组中的最大值。

public int longestValidParentheses (String s) {
// write code here
int maxans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}

发表于 2022-02-10 15:24:02 回复(0)

一只老风铃



	思路：



	初始化一个栈，每遇到左括号  那么将该左括号下标入栈



	遇到右括号时，如果栈中包含左括号，那么这一组括号完成匹配，在对应dp数组位置标记为true



	最后遍历dp数组 找到最长的true长度即为 最长的符合括号匹配条件的长度。

 bool can[100000];//将遍历过程中 合法的括号位置标记为true
    int longestValidParentheses(string s) {
        // write code here
        if(s.size()==0)
            return 0;
        for(int i=0;i<s.size();i++)
            can[i]=false;
        stack<int> my_stack;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(') //左括号 那么Index入栈
                my_stack.push(i);
            else
            {
                if(!my_stack.empty())  //栈非空
                {
                    can[i]=true;
                    can[my_stack.top()]=true;
                    my_stack.pop();//弹出
                    
                }
  
            }
            
        }
        //找到can中最长的连续true长度即可
        int _max=0;
        int i=0;
        for(;i<s.size();i++)
        {
            int num=0;
            while(i<s.size() && can[i]==true)
            {
                i++;
                num++;
            }
            _max=max(_max,num);

            
        }
        return _max;
        
  
        
    }

发表于 2020-07-22 16:15:02 回复(0)

tofine

import java.util.*;
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        Stack<Integer> stack=new Stack<>();
        int max=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(')
                stack.push(i);
            else{
                if(stack.size()==0)
                    stack.push(i);
                else{
                    int top=stack.peek();
                    if(s.charAt(top)=='('){
                        stack.pop();
                        if(stack.size()==0){
                            max=i+1;
                        }
                        else{
                            max=max>i-stack.peek()?max:i-stack.peek();
                        }
                    }
                    else{
                        stack.push(i);
                    }
                }
            }
        }
        return max;
    }
}

发表于 2020-07-17 21:58:40 回复(0)

adssdf

/*很多人会说这道题用动规，可是用动规每次匹配后还要向前到上一个匹配跟这个匹配是否连接，时间复杂度为O(n^2)，其实可以换个想法，用一个bool数组来标记已经匹配过的字符，找到最长的连续标记的长度就是所求的结果。只要遍历两遍数组，时间复杂度为O(n)*/ import java.util.*;
public class Solution {
    public int longestValidParentheses(String s) {
        if(s.length() == 0){
            return 0;
        }
        boolean[] f = new boolean[s.length()];
        char[] chs = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int index = -1,max = 0;
        for(int i =0;i<chs.length;i++){
            if(chs[i] == '('){
                stack.push(i);
            }else{
                if(!stack.empty()){
                    f[i] = true;
                    int t = stack.pop();
                    f[t] = true;
                }
            }
        }
        index = 0;
        for(int i = 0;i<chs.length;i++){
            if(f[i]){
                index++;
                max = max>index?max:index;
            }else{
                index =0;
            }
        }
        return max;
    }
}

发表于 2017-06-08 20:08:14 回复(0)

324134134143428

# 想询问一下各位，有哪些没有考虑到的么？不能ac

class Solution:
    def longestValidParentheses(self , s ):
        if s == "":return 0
        pre = 0
        end = 0
        for i in range(len(s)):
            if s[i]=='(':pre+=1
            elif (s[i]==')') and (pre>0):
                pre-=1
                end+=2
        return end

发表于 2020-09-17 10:45:05 回复(1)

测试小牛进阶

class Solution {

public:

int longestValidParentheses(string s) {

int _max = 0, last = -1;

stack<int> left;

for(int i = 0; i < s.size(); ++i){

if(s[i] == '(') left.push(i);

else{

if(left.empty()) last = i;

else{

left.pop();

if(left.empty()){

_max = max(_max, i - last);

}else{

_max = max(_max, i - left.top());

}

return _max;

}

};

发表于 2016-07-17 15:16:39 回复(0)

小宝12

首先只是记录合法的点然后统计最长连续子串的长度

import java.util.Stack;

public class Solution {

public int longestValidParentheses(String s) {

Stack<Integer> stack = new Stack<Integer>();

int[] S = new int[s.length()];

for(int i=0;i<s.length();i++){

if(s.charAt(i)=='('){

stack.push(i);

}else{

if(!stack.isEmpty()){

S[i] = 1;

S[stack.pop()]=1;

}

int maxLength = 0;

int curLength = 0;

//找到最长怜恤1子串

for(int i=0;i<S.length;i++){

if(S[i]==1){

curLength++;

}else{

curLength=0;

}

if(curLength>maxLength){

maxLength = curLength;

}

return maxLength;

}

发表于 2016-03-10 23:31:56 回复(0)

C/C++

nbgao

class Solution {
public:
    int longestValidParentheses(string s) {
        int l = s.length();         if(s == "" || l<=0)              return 0;                  stack<int> S;         int Max = 0;         int t = -1;         for(int i=0;i<l;i++)          {             if(s[i] == '(')                  S.push(i);                         else{                 if(S.empty())                      t = i;                 else{                     S.pop();                     if(S.empty())                         Max = max(Max, i - t);                     else                         Max = max(Max, i - S.top());                 }             }         }         return Max;
    }
};

发表于 2017-09-28 09:14:00 回复(0)

后劲好大

import java.util.Stack;
public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() <= 0)
        	return 0;
        
        // stack中保存左括弧的index
        Stack<Integer> stack = new Stack<>();
        int maxLen = 0;
        int last = -1;
        for(int i = 0; i < s.length(); i++){
        	// 遇到左括弧就压栈
        	if(s.charAt(i) == '(')
        		stack.push(i);
        	else{
        		// 栈为空，更新起始点的位置
        		if(stack.isEmpty())
        			last = i;
        		else{
        			stack.pop();
        			// 更新合法括弧的长度
        			if(stack.isEmpty())
        				maxLen = Math.max(maxLen, i - last);
        			else
        				maxLen = Math.max(maxLen, i - stack.peek());
        		}      			
        	}
        }
        return maxLen;
    }
}

发表于 2017-05-22 20:55:06 回复(7)

C++

timegogo

很奇怪，为什么使用匹配一对括号长度累加2，括号子串一旦失效累加值归零的方式统计出来的数字会不对（偏大）

代码如下：有大佬能给分析一下吗

int longestValidParentheses(string s) {
        int Max=0,Sum=0;
        stack<char> S;
        for(int i=0;i<s.length();i++){
            if(s[i]==')'){
                if(S.empty()){Sum=0;}
                else{
                    S.pop();
                    Sum+=2;
                    Max = max(Max,Sum);
                }
            }
            else{
                S.push('(');
            }
        }
        return Max;
    }

发表于 2022-05-23 16:33:29 回复(1)

Java

努力学习的中国好青年

import java.util.*;


public class Solution {

    public int longestValidParentheses (String s) {
        Stack<Integer> stack = new Stack<>(); // 设定栈，存储左括号
        stack.push(-1); // 压入-1，处理边界问题
        int res = 0; // 结果存储变量
        
        for (int i = 0;i < s.length();i++) {
            // 如果是左括号则直接入栈
            if (s.charAt(i) == '(') {
                stack.push(i);
            }else {
                // 如果是右括号，则弹栈
                stack.pop();
                // 判空，若栈为空，则说明i左侧已经没有可用的左括号，此时将i压入栈中，防止空栈异常
                if (stack.isEmpty()) {
                    stack.push(i);
                }else {
                    // 长度计算时无需加1，因为预先弹栈，相当于已经加过1，且在01边界上因为初始化时压入-1进栈，因此也得以解决
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        
        return res;
    }
}

发表于 2021-01-31 14:23:50 回复(0)

C++

Spectre_

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // 时间复杂度O(N)，空间复杂度O(N)
        int res = 0, start = -1;
        stack<int> stk;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') stk.push(i);
            else {
                if (stk.empty()) start = i;
                else {
                    stk.pop();
                    if (!stk.empty()) res = max(res, i - stk.top());
                    else res = max(res, i - start);
                }
            }
        }
        return res;
    }
};

发表于 2022-11-10 11:17:37 回复(0)

Python 3

深情的考拉整顿职场

class Solution:
def longestValidParentheses(self, s: str) -> int:
# write code here
dp = [0] * (len(s) + 1)
for i in range(2, len(s) + 1):
if s[i - 1] == ")":
if s[i - 2] == "(":
dp[i] = dp[i - 2] + 2
else:
if i - dp[i - 1] > 1 and s[i - dp[i - 1] - 2] == "(":
dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
return max(dp)

发表于 2022-08-09 17:40:43 回复(0)

Cass998

//用动态规划做速度更快
class Solution {
public:
    int longestValidParentheses(string s) { 
        int n = s.size(), res = 0;
        vector<int> dp(n + 1, 0);//dp[i]表示以当前位置为终点的最长长度，则只能在）处更新
        dp[0] = dp[1] = 0;
        for(int i = 2; i <= n; i++){
            if(s[i - 1] == ')'){
                //如果s[i-2-dp[i-1]]=='('，则说明当前位置可以和i-2-dp[i-1]位置匹配，dp[i]=dp[i-1]+2
                if(s[i - 2 - dp[i - 1]] == '(') dp[i] = dp[i - 1] + 2;
                dp[i] += dp[i - dp[i]];//还要加上匹配位置之前的最长长度dp[i]+=dp[i-dp[i]]
            }   
            res = max(res, dp[i]);
        }
        return res;
    }
};

发表于 2019-02-06 15:17:07 回复(0)

最长的括号子串

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题