32. 最长有效括号
32. 最长有效括号
题目
Given a string containing just the characters '('
and ')'
, return the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = ""
Output: 0
Constraints:
0 <= s.length <= 3 * 10^4
s[i]
is'('
, or')'
.
题目大意
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号 子串 的长度。
解题思路
使用栈来解决这道题。
保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」,初始化为
-1
;栈里其他元素维护左括号的下标。
从前往后遍历字符串:
- 对于遇到的每个
'('
,将它的下标放入栈中; - 对于遇到的每个
')'
,先弹出栈顶元素表示匹配了当前右括号; - 如果栈为空,说明当前的右括号为没有被匹配的右括号,将其下标放入栈中来更新之前提到的「最后一个没有被匹配的右括号的下标」;
- 如果栈不为空,当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」;
- 对于遇到的每个
复杂度分析
- 时间复杂度:
O(n)
,其中n
为字符串的长度,需要遍历整个字符串; - 空间复杂度:
O(n)
,栈的大小在最坏情况下会达到n
。
代码
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
let stack = [-1],
res = 0;
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.length == 0) {
stack.push(i);
} else {
res = Math.max(res, i - stack[stack.length - 1]);
}
}
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
20 | 有效的括号 | [✓] | 栈 字符串 |