32. 最长有效括号

>> 饿了么、美团外卖红包领取地址<<

题目:https://leetcode-cn.com/problems/longest-valid-parentheses/submissions/

代码:

class Solution {
    public int longestValidParentheses(String s) {
        if (s==null || s.length()==0){
            return 0;
        }
        int max = 0;
        int current = 0;
        int sum = 0;
        //正向查找
        for (int i = 0; i < s.length(); i++) {
            sum += s.charAt(i)=='('?1:-1;
            current++;
            if (sum == 0) {
                max = Math.max(max,current);
            }else if (sum<0){
                current = 0;
                sum = 0;
            }
        }
        current = 0;
        sum = 0;
        //反向查找
        for (int i = s.length()-1; i >= 0; i--) {
            sum += s.charAt(i)==')'?1:-1;
            current++;
            if (sum == 0) {
                max = Math.max(max,current);
            }else if (sum<0){
                current = 0;
                sum = 0;
            }
        }
        return max;
    }
}

思路:因为括号只有()这两种符号,那么暂定(=1,)=-1,那么有效符号字串s转换成数字加减之后。和必定是0。

所以遍历字符串,用current来记录每次遍历字串的长度,在sum=0的时候,认为是一个有效的字串,则将其记录起来(因为只需要最长字串,所以只有当max < current的时候才记录)。在sum < 0的时候,这个时候无论字串后面再来什么符号,这个字串肯定是一个无效的字串,所以我们直接将current和sum清零,并从下一位重新开始寻找新的字串。

以上是正向查找的原因,但是为什么正向查找之后还需要反向查找一次并取两次的最大值呢?目的是解决“(()”这种情况,这种情况下如果正向查找的话因为sum还没有为0过,所以得出结果会为0。因为括号的特殊性,所以将其反向查找一遍。反向查找的时候,则认定)=1,(=-1。其他的类似。具体逻辑见代码。

正向反向分别查找之后,取两者的最大值。则这个最大值就是结果。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

维特丝(vetes)泡沫发蜡喷雾干胶定型弹力素羊毛卷男女保湿蓬松发胶 泡沫发蜡450ml+旅行装99ml
¥34.00
维特丝(vetes)一梳黑染发剂染发梳植物潮色显白遮盖白发自然清水纯黑发焗油男女梳炫彩 自然黑LW00
¥49.00
维特丝(vetes)染发笔遮白补染快速染发天然植物一次性染发棒 一次性染发棒黑色
¥46.00
维特丝 护发精油防毛躁清香玫瑰奇焕亮发干枯烫发卷发直发头发润发护发素男女士 滋养柔顺护发精油100ml
¥36.00