给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
字符串长度：
要求时间复杂度 )
,空间复杂度 .
[编程题]最长的括号子串
import java.util.Stack;
public class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() <= 0)
return 0;
// stack中保存左括弧的index
Stack<Integer> stack = new Stack<>();
int maxLen = 0;
int last = -1;
for(int i = 0; i < s.length(); i++){
// 遇到左括弧就压栈
if(s.charAt(i) == '(')
stack.push(i);
else{
// 栈为空，更新起始点的位置
if(stack.isEmpty())
last = i;
else{
stack.pop();
// 更新合法括弧的长度
if(stack.isEmpty())
maxLen = Math.max(maxLen, i - last);
else
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
}
发表于 2017-05-22 20:55:06
回复(7)
//维护一个栈，里面保存'('的下标，每次进入一个')'时，栈弹出，ans更新为当前扫描的下标
//与栈顶元素之间的距离(因为中间可能有些括号已经被消掉了)，因为栈可能为空，所以需要
//记录下起始记录点last。
class Solution {
public:
int longestValidParentheses(string s) {
int ans=0,last=-1;
stack<int> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(') st.push(i);
else{
if(!st.size()) last=i;
else{
st.pop();
if(st.size()) ans=max(ans,i-st.top());
else ans=max(ans,i-last);
}
}
}
return ans;
}
};
发表于 2017-08-05 10:58:14
回复(2)
主要难点在于怎么保存同级之前的匹配，比如()()中的前面的()，可以采用prev：
class Solution(object):
def longestValidParentheses(self, s):
res = 0
stack = []
prev = 0
for i in range(len(s)):
if s[i] == "(":
stack.append(i - prev)
prev = 0
else:
if len(stack) > 0:
prev = i - stack.pop() + 1
res = max(res, prev)
else:
prev = 0
return res
发表于 2017-10-07 23:37:45
回复(0)
第二次做这道题了，更新一下解法吧
解法一是使用堆栈，在leeocode上提交了以后已经提示超时了，所以不推荐这种解法
我记得今年招银？校招有一道类似的题，我当时用的是堆栈，通过率并不高。
直接看代码吧：分别是用堆栈和动态规划求解
/*
* 非动态规划，有时候会超时
*/
public int longestValidParentheses(String s) {
if (s == null || s.length() < 1)
return 0;
Stack<Integer> stack = new Stack<Integer>();
int max = 0, left = -1;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(')
stack.push(i);
else {
if (!stack.isEmpty()) {
stack.pop();
if (!stack.isEmpty())
max = Math.max(max, i - stack.peek());
else
max = Math.max(max, i - left);
} else
left = i;
}
}
return max;
}
// Your runtime beats 92.48 % of java submissions.
public int longestValidParentheses2(String s) {
if (s == null || s.length() == 0)
return 0;
int[] dp = new int[s.length()];
int ans = 0;
for (int i = 1; i < s.length(); i++) {
// 如果是'('直接跳过，默认为0
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(')
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
// 说明s.charAt(i - 1)==')'
else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
// 因为加了一个左括号和一个右括号，所以是加2
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
编辑于 2018-01-06 20:55:00
回复(3)
public static int longestValidParentheses(String s) {
if (s.length() == 0) return 0;
int left = 0;
int right = 0;
int maxLength = 0;
//从左边遍历，左括号则left加1，有括号则right加1
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '('){
left++;
}else {
right++;
}
//left和right相等则最大值为left，
if (left == right){
maxLength = Math.max(maxLength,left);
}else if(left < right){ //如果left小于了right则证明不连续了，将left和right置位0
left = 0;
right = 0;
}
}
left = 0;
right = 0;
//同样的道理，从右往左倒序遍历一次，左括号则left加1，有括号则right加1
for (int i = s.length()-1; i >= 0; i--) {
if (s.charAt(i) == '('){
left++;
}else {
right++;
}
//left和right相等则最大值为left，
if (left == right){
maxLength = Math.max(maxLength,left);
}else if(left > right){//如果left大于了right则证明不连续了，将left和right置位0
left = 0;
right = 0;
}
}
return maxLength*2;
}
发表于 2021-04-08 16:30:32
回复(0)
这题关键的点应该是保存index，而不是保存字符。将index保存在栈中，然后匹配的index会出栈，剩下的就是不能匹配的index。其中有两个细节需要注意，就是栈底应该多个0，栈顶要多个s.size()。原因是对于“（）”这种情况。
int longestValidParentheses(string s)
{
stack<int> sta; int count = 0, max_len = 0; bool fflag = true;
for (int i = 0; i < s.size(); ++i)
{
if (!sta.empty() && s[i] == ')' && s[sta.top()] == '(')
{
sta.pop();
}
else
{
sta.push(i);
}
}
if (sta.empty()) return s.size();
count = s.size();
while (!sta.empty())
{
count = count - sta.top() - 1;
max_len = max(count, max_len);
count = sta.top();
sta.pop();
}
max_len = max(count, max_len);
return max_len;
}
编辑于 2018-03-27 22:02:52
回复(1)
我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以 ‘)’ 结尾，因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值
从前往后遍历字符串求解 dp 值，我们每两个字符检查一次
1、s[i] = ')' 且 s[i-1] = '('，表示字符串形如 ‘......()’，则可推出：
dp[i] = dp[i-2] + 2
以进行这样的转移，是因为结束部分的 "()" 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2
2、s[i] = ')' 且 s[i-1] = ')'，表示字符串形如 ‘......))’，则可推出：
如果s[i - dp[i-1] - 1] = '('，则
dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
考虑如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 subs），对于最后一个‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 subs的前面）。因此，如果子字符串 subs 的前面恰好是 ‘(’ ，那么我们就用 2 加上 subs 的长度（dp[i−1]）去更新 dp[i]。同时，也会把有效子串 “(subs)” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]。
最后的答案即为 dp 数组中的最大值。
public int longestValidParentheses (String s) {
// write code here
int maxans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
// write code here
int maxans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
发表于 2022-02-10 15:24:02
回复(0)
思路：
初始化一个栈，每遇到左括号 那么将该左括号下标入栈
遇到右括号时，如果栈中包含左括号，那么这一组括号完成匹配，在对应dp数组位置标记为true
最后遍历dp数组 找到最长的true长度即为 最长的符合括号匹配条件的长度。
bool can[100000];//将遍历过程中 合法的括号位置标记为true int longestValidParentheses(string s) { // write code here if(s.size()==0) return 0; for(int i=0;i<s.size();i++) can[i]=false; stack<int> my_stack; for(int i=0;i<s.size();i++) { if(s[i]=='(') //左括号 那么Index入栈 my_stack.push(i); else { if(!my_stack.empty()) //栈非空 { can[i]=true; can[my_stack.top()]=true; my_stack.pop();//弹出 } } } //找到can中最长的连续true长度即可 int _max=0; int i=0; for(;i<s.size();i++) { int num=0; while(i<s.size() && can[i]==true) { i++; num++; } _max=max(_max,num); } return _max; }
发表于 2020-07-22 16:15:02
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
Stack<Integer> stack=new Stack<>();
int max=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(')
stack.push(i);
else{
if(stack.size()==0)
stack.push(i);
else{
int top=stack.peek();
if(s.charAt(top)=='('){
stack.pop();
if(stack.size()==0){
max=i+1;
}
else{
max=max>i-stack.peek()?max:i-stack.peek();
}
}
else{
stack.push(i);
}
}
}
}
return max;
}
}
发表于 2020-07-17 21:58:40
回复(0)
/*很多人会说这道题用动规，可是用动规每次匹配后还要向前到上一个匹配跟这个匹配是否连接，时间复杂度为O(n^2)，其实可以换个想法，用一个bool数组来标记已经匹配过的字符，找到最长的连续标记的长度就是所求的结果。只要遍历两遍数组，时间复杂度为O(n)*/ import java.util.*;
public class Solution {
public int longestValidParentheses(String s) {
if(s.length() == 0){
return 0;
}
boolean[] f = new boolean[s.length()];
char[] chs = s.toCharArray();
Stack<Integer> stack = new Stack<>();
int index = -1,max = 0;
for(int i =0;i<chs.length;i++){
if(chs[i] == '('){
stack.push(i);
}else{
if(!stack.empty()){
f[i] = true;
int t = stack.pop();
f[t] = true;
}
}
}
index = 0;
for(int i = 0;i<chs.length;i++){
if(f[i]){
index++;
max = max>index?max:index;
}else{
index =0;
}
}
return max;
}
}
发表于 2017-06-08 20:08:14
回复(0)
# 想询问一下各位，有哪些没有考虑到的么？不能ac
class Solution:
def longestValidParentheses(self , s ):
if s == "":return 0
pre = 0
end = 0
for i in range(len(s)):
if s[i]=='(':pre+=1
elif (s[i]==')') and (pre>0):
pre-=1
end+=2
return end
发表于 2020-09-17 10:45:05
回复(1)
class Solution {
public:
int longestValidParentheses(string s) {
int _max = 0, last = -1;
stack<int> left;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '(') left.push(i);
else{
if(left.empty()) last = i;
else{
left.pop();
if(left.empty()){
_max = max(_max, i - last);
}else{
_max = max(_max, i - left.top());
}
}
}
}
return _max;
}
};
发表于 2016-07-17 15:16:39
回复(0)
首先只是记录合法的点 然后统计最长连续子串的长度
import java.util.Stack;
public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
int[] S = new int[s.length()];
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='('){
stack.push(i);
}else{
if(!stack.isEmpty()){
S[i] = 1;
S[stack.pop()]=1;
}
}
}
int maxLength = 0;
int curLength = 0;
//找到最长怜恤1子串
for(int i=0;i<S.length;i++){
if(S[i]==1){
curLength++;
}else{
curLength=0;
}
if(curLength>maxLength){
maxLength = curLength;
}
}
return maxLength;
}
}
发表于 2016-03-10 23:31:56
回复(0)
class Solution {
public:
int longestValidParentheses(string s) {
int l = s.length(); if(s == "" || l<=0) return 0; stack<int> S; int Max = 0; int t = -1; for(int i=0;i<l;i++) { if(s[i] == '(') S.push(i); else{ if(S.empty()) t = i; else{ S.pop(); if(S.empty()) Max = max(Max, i - t); else Max = max(Max, i - S.top()); } } } return Max;
}
};
发表于 2017-09-28 09:14:00
回复(0)
很奇怪，为什么使用匹配一对括号长度累加2，括号子串一旦失效累加值归零的方式统计出来的数字会不对（偏大）
代码如下：有大佬能给分析一下吗
int longestValidParentheses(string s) {
int Max=0,Sum=0;
stack<char> S;
for(int i=0;i<s.length();i++){
if(s[i]==')'){
if(S.empty()){Sum=0;}
else{
S.pop();
Sum+=2;
Max = max(Max,Sum);
}
}
else{
S.push('(');
}
}
return Max;
}
发表于 2022-05-23 16:33:29
回复(1)
import java.util.*;
public class Solution {
public int longestValidParentheses (String s) {
Stack<Integer> stack = new Stack<>(); // 设定栈，存储左括号
stack.push(-1); // 压入-1，处理边界问题
int res = 0; // 结果存储变量
for (int i = 0;i < s.length();i++) {
// 如果是左括号则直接入栈
if (s.charAt(i) == '(') {
stack.push(i);
}else {
// 如果是右括号，则弹栈
stack.pop();
// 判空，若栈为空，则说明i左侧已经没有可用的左括号，此时将i压入栈中，防止空栈异常
if (stack.isEmpty()) {
stack.push(i);
}else {
// 长度计算时无需加1，因为预先弹栈，相当于已经加过1，且在01边界上因为初始化时压入-1进栈，因此也得以解决
res = Math.max(res, i - stack.peek());
}
}
}
return res;
}
}
发表于 2021-01-31 14:23:50
回复(0)
class Solution {
public:
/**
*
* @param s string字符串
* @return int整型
*/
int longestValidParentheses(string s) {
// 时间复杂度O(N)，空间复杂度O(N)
int res = 0, start = -1;
stack<int> stk;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') stk.push(i);
else {
if (stk.empty()) start = i;
else {
stk.pop();
if (!stk.empty()) res = max(res, i - stk.top());
else res = max(res, i - start);
}
}
}
return res;
}
};
发表于 2022-11-10 11:17:37
回复(0)
class Solution:
def longestValidParentheses(self, s: str) -> int:
# write code here
dp = [0] * (len(s) + 1)
for i in range(2, len(s) + 1):
if s[i - 1] == ")":
if s[i - 2] == "(":
dp[i] = dp[i - 2] + 2
else:
if i - dp[i - 1] > 1 and s[i - dp[i - 1] - 2] == "(":
dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
return max(dp)
def longestValidParentheses(self, s: str) -> int:
# write code here
dp = [0] * (len(s) + 1)
for i in range(2, len(s) + 1):
if s[i - 1] == ")":
if s[i - 2] == "(":
dp[i] = dp[i - 2] + 2
else:
if i - dp[i - 1] > 1 and s[i - dp[i - 1] - 2] == "(":
dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
return max(dp)
发表于 2022-08-09 17:40:43
回复(0)
//用动态规划做速度更快
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size(), res = 0;
vector<int> dp(n + 1, 0);//dp[i]表示以当前位置为终点的最长长度，则只能在）处更新
dp[0] = dp[1] = 0;
for(int i = 2; i <= n; i++){
if(s[i - 1] == ')'){
//如果s[i-2-dp[i-1]]=='('，则说明当前位置可以和i-2-dp[i-1]位置匹配，dp[i]=dp[i-1]+2
if(s[i - 2 - dp[i - 1]] == '(') dp[i] = dp[i - 1] + 2;
dp[i] += dp[i - dp[i]];//还要加上匹配位置之前的最长长度dp[i]+=dp[i-dp[i]]
}
res = max(res, dp[i]);
}
return res;
}
};
发表于 2019-02-06 15:17:07
回复(0)
问题信息
难度：
109条回答
912收藏
26944浏览
通过挑战的用户
-
2023-02-02 14:09:33
-
2022-12-24 18:26:17
-
2022-10-07 19:18:26 -
2022-09-16 16:31:39 -
2022-09-16 11:30:00
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
