欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode初学——最长有效括号

程序员文章站 2024-03-14 21:56:05
...

题目:

Leetcode初学——最长有效括号

这道题目我是采用一种左右遍历的方法写的

先从左往右遍历,再从右往左遍历一次,寻找最长的有效括号集

在这个过程中,我们定义两个参数 left和right 分别记录遇到的左括号和右括号的次数,当right==left时,我们记录下长度,最终取最长的长度

图解如下:

Leetcode初学——最长有效括号

先从左往右遍历

Leetcode初学——最长有效括号

在到第二个括号时 left==right==1

maxCount=2;

之后再往后都没有left与right相等的情况

接着,我们从右往左遍历

Leetcode初学——最长有效括号

从右往左的第四个字符时,我们又取到了right==left==2

maxCount=4

Leetcode初学——最长有效括号

这个时候我们取到了left>right的情况,遇到这种情况,我们需要把left和right都归零  同理,从左往右取的时候也有同样的情况,请读者自行判断

再接着

Leetcode初学——最长有效括号

 

left==right==1

maxCount=4>2

所以maxCount还为4

 

代码:

class Solution {
    public int longestValidParentheses(String s) {
        int left=0;
        int right=0;
        int maxCount=0;
        //从左往右遍历
        for(int i=0;i<s.length();i++){
            switch (s.charAt(i)){
                case '(': left++;break;
                case ')': right++;break;
                default:break;
            }
            if(right>left) {
                left=0;
                right=0;
                continue;
            }
            if(left==right && 2*left>maxCount)
                maxCount=2*left;
        }
        //归零
        left=0;
        right=0;
        //从右往左遍历
        for(int i=1;i<=s.length();i++){
            switch (s.charAt(s.length()-i)){
                case '(': left++;break;
                case ')': right++;break;
                default:break;
            }
            if(left>right) {
                left=0;
                right=0;
                continue;
            }
            if(left==right && 2*left>maxCount)
                maxCount=2*left;
        }

        return maxCount;
    }
}

 

结果:

Leetcode初学——最长有效括号

相关标签: Leetcode学习