给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
字符串长度：
要求时间复杂度 )
,空间复杂度 .
[编程题]最长的括号子串
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
// 固定套路的分类讨论dp
// 定义子问题：以i结尾的最长括号字串
// 情况1：以(结尾，就是0
// 情况2：以)结尾，那就到子问题的最长括号的起始位置的前一个位置，看能否有"("
int len = s.length();
int res = 0;
int[] dp = new int[len + 1];
for(int i = 1; i <= len; i++) {
if(s.charAt(i - 1) == ')' && (i - dp[i - 1] - 2 >= 0) && s.charAt(i - dp[i - 1] - 2) == '(') {
dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;
}
res = Math.max(res, dp[i]);
}
return res;
}
}
编辑于 2024-01-10 11:52:41
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
// 参考：https://b23.tv/1MZoUWh
public int longestValidParentheses (String s) {
// write code here
// dp[i]表示以s.charAt(i)结尾的最长子括号子串
int[] dp = new int[s.length()];
int max = 0;
// 以左括号结尾的dp肯定为0,因此递推公式只需要考虑右括号结尾即可
for (int i = 1; i < s.length(); i++) {
// s.charAt(i) == ')'表示s的i位置字符为右括号，右括号才能与i之前的左括号闭合成正确的子串
// i - dp[i - 1] - 1为是与当前右括号闭合的左括号的下标，当前右括号的下标为i，i-1的最长括号
// 子串长度为dp[i-1],则当前右括号闭合的左括号的下标为i - dp[i - 1] - 1。dp[i-1]的值只考虑
// 当前右括号和当前右括号闭合的左括号所夹区域的括号。(i - dp[i - 1] - 1) < 0表示当前右括号
// 无闭合的左括号，即向左去寻找闭合的左括号，寻至首个也首字符也未找到，直至越界，则此时
// 应有dp[i]=0,dp已经初始化为0
// s.charAt(i - dp[i - 1] - 1) == '('表示找到当前右括号闭合的左括号，只有找到闭合的左括号
// dp[i]才能不计为0
if (s.charAt(i) == ')' && (i - dp[i - 1] - 1) >= 0 && s.charAt(i - dp[i - 1] - 1) == '('){
// 2表示当前右括号与左括号的长度。dp[i - 1] 表示以当前右括号的前一个括号结尾的s的长度，即
// 当前右括号和与它闭合的左括号所夹的最长子串长度。dp[i - dp[i - 1] - 2]表示当前右括号的闭合
// 左括号的前一个括号的对应的最长子串长度，越界时计为0
dp[i] =2 + dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
max = Math.max(max, dp[i]);
}
return max;
}
}
发表于 2023-11-01 16:08:41
回复(0)
public int longestValidParentheses (String s) {
//长度：当前索引-栈顶索引
Stack<Integer> st=new Stack<>();
st.push(-1);//避免第一个是），造成异常，初始化栈顶为-
int ans=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='('){//栈记录左括号下标，左括号入栈
st.push(i);
}else{
st.pop();//遇到右括号，弹出左括号下标
if(st.isEmpty()){//栈为空，记录上一次结束的位置
st.push(i);
}else{//栈不空，说明栈中还有左括号，右括号不够用，减去栈顶位置就是长度
ans=Math.max(ans,i-st.peek());//长度更新为：当前下标和栈顶下标的距离 （括号长度）
}
}
}
return ans;
}
发表于 2023-07-23 10:59:14
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
// 单序列问题，每一位存储以当前位置结尾的最长子串长度
if(s.length()<=1)return 0;
int len=s.length();
int[] dp=new int[len];
int l=0;
int res=0;
Stack<Integer> stack=new Stack();
while(l<len){
// 如果当前是左括号，入栈
if(s.charAt(l)=='('){
stack.push(l);
l++;
}
else{
// 如果是右括号，出栈
if(stack.isEmpty()){
l++;
}
else{
int top=stack.pop();
dp[l]=l-top+1;
if(top>0){
dp[l]+=dp[top-1];
}
res=Math.max(res,dp[l]);
l++;
}
}
}
return res;
}
}
其实不需要记录连续括号上次结束位置的
发表于 2023-03-11 17:36:29
回复(0)
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
int len = s.length();
if(len == 0){
return 0;
}
// 定义dp， dp[i] = 当前0 ~ i个字符，有效括号的长度
int[] dp = new int[len];
char[] chars = s.toCharArray(); // 字符数组
int result = 0; // 返回值
int pre = -1; // 指向
// 遍历字符数组，从1开始，因为0位置无论是左括号 还是 右括号，能组成的有效括号长度都是0
for (int i = 1; i < chars.length; i++) {
// i只匹配右括号，遇到左括号它并不能组成括号，所以忽略
if(chars[i] == ')'){
// 当i是 ) 时，需要看 i - 1 位置的有效括号长度是多少，
// 假设此时i = 3， i-1的位置 在dp中记录的有效长度是2，
// 那么需要向前看 i - 2 - 1位置，也就是i-1有效长度的再前一个位置的结果
pre = i - dp[i - 1] - 1;
// 如果这个pre不越界，并且在char数组中等于( ，那么说明它能跟当前i字符) 匹配成一个有效括号
if(pre >= 0 && chars[pre] == '('){
// 那么dp[i] 的有效括号长度，最起码是 dp[i-1] + 2
// 但还需要再累加上 pre-1的索引在dp记录的有效长度，如果越界则累加0，如果不越界，则累加dp[pre - 1]
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
}
}
// 每次循环都将dp[i] 与 result 取最大值
result = Math.max(result, dp[i]);
}
// 循环结束，result为解
return result;
}
}
发表于 2022-12-01 13:54:41
回复(0)
这道题有两种思路，一种是基于栈，一种是基于动态规划递推。我个人感觉这种题用动态规划做的话，缺少拓展性。而基于栈的思路也是融合了动态规划的思想、
本方法是基于栈的方法。
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
int[] dp = new int[s.length()+1];
LinkedList<Integer> stack = new LinkedList();
int maxNum = 0;
for(int i=1;i<s.length()+1;i++){
if(s.charAt(i-1)=='('){
stack.addLast(i);
}
else if(!stack.isEmpty()){
int left = stack.removeLast();
dp[i] = i - left + 1;
dp[i] += dp[left-1];
}
maxNum = Math.max(maxNum, dp[i]);
}
return maxNum;
}
}
发表于 2022-09-23 18:29:24
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
Deque<Integer> stack = new ArrayDeque<>();
int n = s.length();
int[] flag = new int[n];
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') stack.push(i);
else {
if (stack.isEmpty()) flag[i] = 1;
else stack.pop();
}
}
while (!stack.isEmpty()) {
flag[stack.pop()] = 1;
}
int res = 0, l = 0;
for (int i = 0; i < n; i++) {
if (flag[i] == 1) {
l = 0;
continue;
}
l++;
res = Math.max(res, l);
}
return res;
}
}
发表于 2022-09-19 16:15:32
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
if(s.length()==0){return 0;}
if(s.length()==1){return 0;}
Deque<Integer> stack=new LinkedList<Integer>();
ArrayList<Integer> list=new ArrayList<Integer>();
for(int i=0;i<=s.length()-1;i++){
char c=s.charAt(i);
if(c=='('){stack.push(i);}
if(c==')'){
if(!stack.isEmpty()){
list.add(stack.pop());
list.add(i);
}
}
}
return max_length(list);
}
public int max_length(ArrayList<Integer> list){
if(list.isEmpty()){return 0;}
Collections.sort(list);
int[] arr=new int[list.size()];
for(int i=0;i<=list.size()-1;i++){
arr[i]=list.get(i);
}
int[] dp=new int[arr.length];
dp[0]=1;
for(int i=1;i<=arr.length-1;i++){
if(arr[i-1]==arr[i]-1){
dp[i]=dp[i-1]+1;
}else{
dp[i]=1;
}
}
int max=dp[0];
for(int i=0;i<=dp.length-1;i++){
max=dp[i]>max?dp[i]:max;
}
return max;
}
}
发表于 2022-08-14 13:57:22
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
int len = s.length();
if(len == 0) return 0;
int max = 0;
int l = 0 , r = 0;
for(int i = 0; i < len; i++){
if(s.charAt(i) == '('){
l++;
}
if(s.charAt(i) == ')'){
r++;
}
if(l == r){
max = max > 2 * r ? max : 2 * r;
}
if(l < r){
l = 0;
r = 0;
}
}
l = 0;
r = 0;
for(int i = len - 1; i >= 0 ;i--){
if(s.charAt(i) == '('){
l++;
}
if(s.charAt(i) == ')'){
r++;
}
if(l == r){
max = max > 2 * r ? max : 2 * r;
}
if(l > r){
l = 0;
r = 0;
}
}
return max;
}
}
发表于 2022-05-12 20:32:21
回复(0)
import java.util.*;
public class Solution {
/**
* 双指针写法
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
int left = 0;
int right = 0;
int res = 0;
for (int i = 0; i < s.length(); ++i){
char ch = s.charAt(i);
if (ch == '('){
left++;
} else {
right++;
}
if (left == right){
res = Math.max(res, 2 * left);
} else if (left < right){
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; --i){
if (s.charAt(i) == '('){
left++;
} else {
right++;
}
if (left == right){
res = Math.max(res, 2 * left);
} else if (left > right){
left = right = 0;
}
}
return res;
}
/**
* 栈写法
*/
public int longestValidParentheses2 (String s) {
// write code here
int res = 0;
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.offerLast(-1);
for (int i = 0; i < s.length(); ++i){
char ch = s.charAt(i);
if (ch == '('){
stack.offerLast(i);
} else {
stack.pollLast();
if (stack.isEmpty()){
stack.offerLast(i);
} else {
res = Math.max(res, i - stack.peekLast());
}
}
}
return res;
}
}
public class Solution {
/**
* 双指针写法
* @param s string字符串
* @return int整型
*/
public int longestValidParentheses (String s) {
// write code here
int left = 0;
int right = 0;
int res = 0;
for (int i = 0; i < s.length(); ++i){
char ch = s.charAt(i);
if (ch == '('){
left++;
} else {
right++;
}
if (left == right){
res = Math.max(res, 2 * left);
} else if (left < right){
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; --i){
if (s.charAt(i) == '('){
left++;
} else {
right++;
}
if (left == right){
res = Math.max(res, 2 * left);
} else if (left > right){
left = right = 0;
}
}
return res;
}
/**
* 栈写法
*/
public int longestValidParentheses2 (String s) {
// write code here
int res = 0;
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.offerLast(-1);
for (int i = 0; i < s.length(); ++i){
char ch = s.charAt(i);
if (ch == '('){
stack.offerLast(i);
} else {
stack.pollLast();
if (stack.isEmpty()){
stack.offerLast(i);
} else {
res = Math.max(res, i - stack.peekLast());
}
}
}
return res;
}
}
发表于 2022-03-04 14:54:33
回复(0)
我们定义 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)
public int longestValidParentheses (String s) {
// write code here
int res = 0;
int[] dp = new int[s.length()];
char[] arr = s.toCharArray();
for(int i = 1; i < arr.length; i++){
if(arr[i] == ')'){
if(arr[i-1] == '('){
dp[i] = (i >= 2 ? dp[i-2] : 0)+2;
}else if(i >= 1+dp[i-1] && arr[i-1-dp[i-1]] == '('){
dp[i] = dp[i-1]+2+ (i >= dp[i-1]+2 ? dp[i-dp[i-1]-2] : 0);
}
res = Math.max(res,dp[i]);
}
}
return res;
}
// write code here
int res = 0;
int[] dp = new int[s.length()];
char[] arr = s.toCharArray();
for(int i = 1; i < arr.length; i++){
if(arr[i] == ')'){
if(arr[i-1] == '('){
dp[i] = (i >= 2 ? dp[i-2] : 0)+2;
}else if(i >= 1+dp[i-1] && arr[i-1-dp[i-1]] == '('){
dp[i] = dp[i-1]+2+ (i >= dp[i-1]+2 ? dp[i-dp[i-1]-2] : 0);
}
res = Math.max(res,dp[i]);
}
}
return res;
}
发表于 2021-08-22 21:20:52
回复(0)
public int longestValidParentheses(String s) {
if (s == null || s.length() < 2) {
return 0;
}
int[] dp = new int[s.length()];
if (s.charAt(0) == '(' && s.charAt(1) == ')') {
dp[1] = 2;
}
int res = Math.max(dp[1], 0);
for (int i = 2; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = 2 + dp[i - 2];
} else {
int index = i - dp[i - 1] - 1;
if (index >= 0 && s.charAt(index) == '(') {
dp[i] = 2 + dp[i - 1];
if (index - 1 >= 0) {
dp[i] += dp[index - 1];
}
}
}
}
res = Math.max(res, dp[i]);
}
return res;
}
发表于 2021-08-16 20:33:23
回复(0)
int max=0,n=s.length();
int[]dp=new int[n];//dp[i]表示以i结尾的括号子串的长度
for(int i=1;i<n;i++){
if(s.charAt(i)==')'){//只对右括号的情况进行分析
if(s.charAt(i-1)=='('){
dp[i]=(i<2?0:dp[i-2])+2;
}
else{ //如果j=i-dp[i-1]-1位置（也就是dp[i-1]括号字串的前一个元素）是'(',则增加了匹配长度
//那么扩展之后的字串长度=dp[i-1]的长度+2+dp[j-1]位置匹配的长度
int j=i-dp[i-1]-1;
if(j>=0&&s.charAt(j)=='('){
dp[i]=dp[i-1]+(j-1>=0?dp[j-1]:0)+2;//2是i位置的）和j位置的(匹配的
}
}
}
max=Math.max(max,dp[i]);
}
return max;
发表于 2021-03-25 10:30:18
回复(0)
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)
问题信息
难度：
22条回答
912收藏
26025浏览
通过挑战的用户
-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
