#yyds干货盘点# 面试必刷TOP101：最长的括号子串

1.简述：

描述

给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .

例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .

字符串长度：

要求时间复杂度  ,空间复杂度 .

示例1

输入：

"(()"

返回值：

2

示例2

输入：

"(())"

返回值：

4

2.代码实现：

import java.util.*;
public class Solution {
    public int longestValidParentheses (String s) {
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1; 
        Stack<Integer> st = new Stack<Integer>();
        for(int i = 0; i < s.length(); i++){
            //左括号入栈
            if(s.charAt(i) == '(') 
                st.push(i);
            //右括号
            else{ 
                //如果右括号时栈为空，不合法，设置为结束位置
                if(st.isEmpty()) 
                    start = i;
                else{
                    //弹出左括号
                    st.pop(); 
                    //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if(!st.empty()) 
                        res = Math.max(res, i - st.peek());
                    //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else 
                        res = Math.max(res, i - start);
                }
            }
        }
        return res;
    }
}