最长有效括号

[编程题]最长有效括号

热度指数：274 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

示例1

输入

"(()"

输出

算法知识视频讲解

Java

青春猪头少年不会没有offer

用栈来做。

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String s = in.next();
        int n = s.length() - 2;
        Deque<Character> stk = new ArrayDeque<>();
        for (char ch: s.toCharArray()) {
            if (ch != '(' && ch != ')') continue;
            if (ch == '(') stk.push(ch);
            else if (ch == ')'){
                if (!stk.isEmpty() && stk.peek() == '(') stk.pop();
                else stk.push(ch);
            }
        }
        System.out.println(n - stk.size());
    }
}

发表于 2024-02-22 22:34:54 回复(0)

皮卡皮卡01001！

双指针方法做
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        int l=0,r=s.length()-1;
        Stack<Character> sk1=new Stack<>();
        int len=0;
        while(l<r){
            if(s.charAt(l)=='('){
                sk1.add('(');
            }
            l++;
            if(s.charAt(r)==')'){
                if(!sk1.isEmpty()){
                    len+=2;
                    r--;
                }
            }else r--;
            
        }
        return len;
    }
}

发表于 2021-10-21 14:57:21 回复(0)

王治珺

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
int max = 0,start = 0;
if(null == s) return 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0;i<s.length();i++){
if('(' == s.charAt(i)){
stack.push(i);
continue;
}else {
if(stack.isEmpty()){
start = i + 1;
continue;
}else {
stack.pop();
if(stack.isEmpty()){
max = Math.max(max, i - start+1);
}else {
max = Math.max(max, i - stack.peek());
}
}
}
}
return max;
}
}

发表于 2021-02-21 11:22:09 回复(0)