LC32—最长有效括号
32. 最长有效括号
难度困难1185
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()利用栈:
思想:我们始终保持栈底元素为当前已经遍历过的元素中(最后一个没有被匹配的右括号的下标),这样的作法就是考虑边界条件的处理,栈里的其他元素维护左括号的下标
- 对于遇到的每个
"(",我们将它的下标放入栈中 - 对于遇到的每个
)，我们先弹出栈顶元素表示匹配了当前右括号 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标] 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
package com.nie.o2;/* * *@auth wenzhao *@date 2021/2/24 22:15 */
import java.util.Deque;
import java.util.LinkedList;
public class LEE32 {
public static void main(String[] args) {
String s = "()))((())";
System.out.println(longestValidParentheses(s));
}
public static int longestValidParentheses(String s) {
int maxans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.size() == 0) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
}动态规划
在这里插入图片描述
在这里插入图片描述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-APIzRDpS-1614824038777)(C:/Users/LENOVO/AppData/Roaming/Typora/typora-user-images/image-20210304100251855.png)]
注意:s = " " + s; 可以减少判断次数
public int longestValidParentheses1(String s) {
int max = 0;
s = " " + s;
int dp[] = new int[s.length()];
for (int i = 2; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = dp[i - 2] + 2;
} else if (s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
}
max = Math.max(max, dp[i]);
}
}
return max;
}根据括号的特性查找
public class Solution {
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right > left) {
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) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxlength;
}
}
本文来源面相薪水编程，由javajgs_com转载发布，观点不代表Java架构师必看的立场，转载请标明来源出处
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录