题解 | #最长的括号子串# 痛定思痛 字节一面算法题

面试官要求时间复杂度为O(n)，空间复杂度为O(1)

public class Solution {
    public int longestValidParentheses (String s) {
        int left =0,right =0, maxLen = 0;
        for(int i=0;i<s.length()-1;i++){
            if(s.charAt(i)=='(') left++;
            else right++;
            if(left==right) maxLen = Math.max(maxLen,2*right);
            else if(right>left) left =right = 0;
        }
        left =right = 0;
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='(') left++;
            else right++;
            if(left==right) maxLen = Math.max(maxLen,2*right);
            else if(left>right) left=right=0;
        }
        return maxLen;
    }
}

鄙人大菜鸡一个，只写出来了时间复杂度为O(n)，空间复杂度为O(n)

public class Solution {
    public int longestValidParentheses(String s) {
        int res = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') 
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') 
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}