题意整理

• 给出一个长度为n的，仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。
• 格式正确的括号子串是指每一个左右括号都能相互抵消掉。

方法一（栈）

1.解题思路

• 首先新建一个栈，用于存放出现左括号字符对应的下标。
• 遍历字符串，如果当前是左括号，直接将下标入栈。如果是右括号，弹出栈顶元素，此时栈不为空的化，更新格式正确的括号子串长度，取较大者；如果为空，则重置子串起点。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        //记录最长的格式正确的括号子串的长度
        int max=0;
        //新建栈
        Stack<Integer> st=new Stack<>();
        st.push(-1);
        for(int i=0;i<s.length();i++){
            //将左括号出现下标入栈
            if(s.charAt(i)=='('){
                st.push(i);
            }
            else{
                //如果遇到右括号，弹出栈顶元素
                st.pop();
                //此时栈顶元素后一位到i之间正好是格式正确的括号子串，更新长度，取较大者
                if(!st.isEmpty()){
                    max=Math.max(max,i-st.peek());
                }
                //如果为空，需要重置子串起点
                else{
                    st.push(i);
                }
            }
        }
        return max;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历字符串中所有字符，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外大小为n的栈，所以空间复杂度为$O(n)O(n)$。

方法二（双指针）

1.解题思路

• 新建两个变量left和right，分别记录左右括号出现次数。
• 正向遍历一次字符串，如果左右括号相等，则更新格式正确的括号子串长度，取较大者。如果左括号数小于右括号数，说明有不合法右括号（前面没有左括号与之匹配），重置为0。
• 最后反向遍历一次字符串，如果左右括号相等，则更新格式正确的括号子串长度，取较大者。如果左括号数大于右括号数，说明有不合法左括号（后面没有右括号与之匹配），重置为0。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        int max=0;
        //分别记录左右括号出现次数
        int left=0,right=0;
        //正向遍历
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                left++;
            }
            else{
                right++;
            }
            //如果左右括号相等，则更新格式正确的括号子串长度，取较大者
            if(left==right){
                max=Math.max(max,right*2);
            }
            //如果左括号数小于右括号数，说明有不合法右括号，重置为0
            else if(left<right){
                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){
                max=Math.max(max,left*2);
            }
            //如果左括号数大于右括号数，说明有不合法左括号，重置为0
            else if(left>right){
                left=right=0;
            }
        }
        
        return max;
    }
}

3.复杂度分析

• 时间复杂度：需要正向遍历、反向遍历字符串各一次，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：不需要额外的空间，所以空间复杂度为$O(1)O(1)$。