友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
32. 最长有效括号
给你一个只包含 ( 和 ) 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
-
0 <= s.length <= 3 * 104 -
s[i]为(或)
思路分析
使用栈记录左右括号的下标，做匹配，同时用于标注“占位符”的状态。遍历完成后，统计占位符中的数量，找出最大长度。
官方题解中的栈，除了栈，不需要额外空间，把前置下标放入栈中，用于统计长度，解法非常巧妙。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-23 16:49:57
*/
public int longestValidParentheses(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
boolean[] holder = new boolean[s.length()];
List<Integer> stack = new ArrayList<>(s.length());
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.add(i);
} else if (c == ')') {
if (!stack.isEmpty()) {
holder[i] = true;
holder[stack.removeLast()] = true;
}
}
}
int result = 0;
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
if (holder[i]) {
cnt++;
result = Math.max(result, cnt);
} else {
cnt = 0;
}
}
return result;
}
参考资料
-
32. 最长有效括号 - 官方题解 — 官方题解中的栈，除了栈，不需要额外空间，把前置下标放入栈中，用于统计长度，解法非常巧妙。