#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;
}
}