T32.最长有效括号
stack, 双向计数(贪心), https://leetcode.cn/problems/longest-valid-parentheses/
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号 子串 的长度。
左右括号匹配,即每个左括号都有对应的右括号将其闭合的字符串是格式正确的,比如 "(()())"。
示例 1:
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"示例 2:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"示例 3:
输入:s = ""
输出:0提示:
0 <= s.length <= 3 * 104s[i]为'('或')'
解决这道题有多种方法,其中栈(Stack)和双向计数(贪心,
方法一:栈(推荐,清晰直观)
解题思路
我们使用栈来记录括号的下标:
- 始终让栈底保存“最后一个没有被匹配的右括号的下标”(作为有效括号子串的起始基准点)。
- 初始化栈,压入
-1作为基准。 - 遍历字符串:
- 遇到
'(':将当前下标压入栈中。 - 遇到
')':先将栈顶元素弹出。- 弹出后如果栈变为空:说明当前的
')'没有匹配的'(',它成为了新的“未被匹配的右括号”,因此把当前下标压入栈,作为新的基准点。 - 弹出后如果栈不为空:说明当前的
')'成功与某个'('匹配,此时以当前位置结尾的有效括号长度为i - 栈顶下标,用其更新最大长度即可。
- 弹出后如果栈变为空:说明当前的
- 遇到
C++ 代码实现
cpp
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1); // 初始化基准点
int max_len = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
stk.push(i);
} else {
stk.pop();
if (stk.empty()) {
// 当前 ')' 无法被匹配,成为新的基准点
stk.push(i);
} else {
// 计算以当前位置为结尾的有效子串长度
max_len = max(max_len, i - stk.top());
}
}
}
return max_len;
}
};复杂度分析
- 时间复杂度:
,只需遍历一次字符串。 - 空间复杂度:
,栈最多存放 个元素。
方法二:双向遍历计数法(最优空间 )
解题思路
利用两个计数器 left 和 right 分别记录 '(' 和 ')' 的个数:
- 从左向右遍历:
- 遇到
'('则left++,遇到')'则right++。 - 当
left == right时,说明找到了一个合法括号子串,长度为2 * right,更新最大值。 - 当
right > left时,说明当前右括号过多,已不可能合法,重置left = 0, right = 0。
- 遇到
- 问题:形如
"(()"的情况,left一直大于right,无法触发left == right。 - 解决:再从右向左遍历一次:
- 规则镜像:当
left > right时,说明当前左括号过多,重置left = 0, right = 0;当left == right时更新最大值。
- 规则镜像:当
C++ 代码实现
cpp
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0, right = 0, max_len = 0;
int n = s.length();
// 从左到右遍历
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
max_len = max(max_len, 2 * right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
// 从右到左遍历
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
max_len = max(max_len, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return max_len;
}
};复杂度分析
- 时间复杂度:
,两次线性扫描。 - 空间复杂度:
,仅需常数额外变量。