/**
* 【最长的括号子串】
* 给出一个长度为 n 的,仅包含字符 '(' 和 ')' 的字符串,计算最长的格式正确的括号子串的长度。
* "(()" => 2
* "(())" => 4
* 分析:栈——栈顶压入-1,遇到"("就把下标压栈,遇到")"就弹出一个数字扔掉,求当前角标-剩余栈顶角标值
*
* @author xuan
* @create 2021-10-27 10:33
**/
public class ZuiChangKuoHaoZiChuan {
public static void main(String[] args) {
String str = "())(())";
System.out.println(longestValidParentheses(str));
}
public static int longestValidParentheses(String s) {
int maxLen = 0;
Deque<Integer> deque = new ArrayDeque<>();
deque.push(-1);
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
deque.push(i);
} else {
//只要是")"先弹栈扔一个
deque.pop();
if (deque.isEmpty()) {
//空了就push
deque.push(i);
} else {
maxLen = Math.max(i - deque.peek(), maxLen);
}
}
}
return maxLen;
}
}
最长的括号子串
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 0. 链接 1. 需求 Given a string containing just the characters...
- 算法-面试题系列(一)➡️题目三➡️子串最长括号有效配对 括号有效配对是指: 任何一个左括号都能找到和其正确配对的...