6
#yyds干货盘点# 面试必刷TOP101：最长的括号子串
source link: https://blog.51cto.com/u_15488507/5737572
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：最长的括号子串
精选 原创1.简述：
描述给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
字符串长度：
要求时间复杂度 ,空间复杂度 .
示例1"(()"
"(())"
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;
}
}
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;
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK