当前位置：首页 > article >正文

LeetCode【32】最长的有效括号

article 2025/1/15 16:30:45

题目：
在这里插入图片描述

思路：

括号字符串依次入栈，删除匹配的成对括号。最后栈中留下的都是无法匹配的断点。这些断点的差值减一就是断点间有效括号串的长度，取这些长度的最大值即可。
例如括号字符串 “)()((())(”，最后留在栈中的字符下标为 0 3 8。根据这三个断点可以得到，两个有效括号子串的长度分别为 3-0-1 = 2 和 8-3-1=4。所以最长的长度就是 4。

https://www.jianshu.com/p/e6b6e3b964d8

代码：

public int longestValidParentheses(String s) {
    if(s.length() <= 1) return 0;
    List<Integer> stack = new ArrayList<>();
    for(int i = 0; i < s.length(); ++i){
        if(!stack.isEmpty() 
                && s.charAt(i) == ')' 
                && s.charAt(stack.get(stack.size()-1)) == '(') stack.remove(stack.size()-1);
        else stack.add(i);
    }
    stack.add(s.length());
    int longest = stack.get(0);
    int diff;
    for(int i = 1; i < stack.size(); ++i){
        if((diff = stack.get(i)-stack.get(i-1)-1) > longest) longest = diff;
    }
    return longest;
}