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。其他的类似。具体逻辑见代码。

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