题目
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
示例 3:
输入:s = ""
输出:0
提示:
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
暴力枚举
超时
public static int longestValidParentheses(String s) {
int max=0;
for (int i = 0; i < s.length(); i++) {
for (int j = s.length(); j >=i ; j--) {
if(j-i<max)
{
break;
}
String temp = s.substring(i,j);
if(isTrueKuoHao(temp))
{
max=Math.max(max,temp.length());
break;
}
}
}
return max;
}
public static boolean isTrueKuoHao(String s)
{
if(s.length()==0)
{
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i)=='(')
{
stack.push('(');
}
else
{
if(!stack.isEmpty())
{
stack.pop();
}
else
{
return false;
}
}
}
return stack.isEmpty();
}
双指针遍历
- 解题思路
左括号数量一定大于等于右括号数量,当左括号数量小于有括号数量的时候,重新计算长度,当等于右括号数量的时候,计算一下最大长度。
public static int longestValidParentheses2(String s) {
int max=0;
for (int i = 0; i < s.length()-1; i++) {
if(s.charAt(i)!='(')
{
continue;
}
int left=1;
int right=0;
for (int j = i+1; j < s.length(); j++) {
if(s.charAt(j)=='(')
{
left++;
}
else
{
right++;
}
if(right>left)
{
break;
}else if(left==right)
{
max=Math.max(max,left+right);
}
}
}
return max;
}
栈
- 解题思路
先往栈中压入一个-1,然后循环遍历这个字符串,当等于左括号时,压序号入栈,当等于右括号时,出栈。然后判断栈空没有,空了的话,插入当前序号入栈,表示当前序号分割了括号的连续;不空的情况,可以计算一下当前连续括号的长度
public static int longestValidParentheses3(String s)
{
Stack<Integer> stack =new Stack<>();
stack.push(-1);
int len = 0;
int maxLen=0;
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i)=='(')
{
stack.push(i);
}
else
{
stack.pop();
if(stack.isEmpty())
{
stack.push(i);
}
else
{
int pre = stack.peek();
len = i-pre;
maxLen=Math.max(len,maxLen);
}
}
}
return maxLen;
}
标签:有效,int,max,++,最长,括号,length,stack
From: https://www.cnblogs.com/huacha/p/16870822.html