32. 最长有效括号
一句话套路栈底存最后一个破坏位 / 也可区间 DP
题目描述
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号 子串 的长度。
左右括号匹配,即每个左括号都有对应的右括号将其闭合的字符串是格式正确的,比如 "(()())"。
示例 1:
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"
示例 3:
输入:s = "" 输出:0
提示:
0 <= s.length <= 3 * 104s[i]为'('或')'
思路
时间
O(n)思路
思路(栈,最好记):栈底始终存「最后一个破坏合法性的位置」,初始压 -1。
遇 '(' 压下标;遇 ')' 先弹一个:
- · 弹完栈空 -> 这个 ')' 成为新的分隔符,压下它的下标;
- · 否则栈顶就是当前匹配段的「左边界前一位」,长度 = i - 栈顶。
思路(DP)
dp[i] = 以 i 结尾的最长有效长度。
s[i]==')' 时看 s[i-1]:是 '(' 则 dp[i]=dp[i-2]+2;
是 ')' 则看 s[i-dp[i-1]-1] 是否为 '(',是则再拼上前面的 dp[i-dp[i-1]-2]。
思路(双指针)
左右各扫一遍,open==close 时更新、close>open 时归零 ——为什么必须扫两遍?因为 "(()" 只有左到右扫会漏掉。
图解
有效段
()() 长度 4(下标 1..4)。思路:存下标做栈,用「上一个不匹配位置」当左界,每段长度 = i - 栈顶。逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0032 {
class Solution {
public:
static int longestValidParentheses(const string& s) {
int ans = 0;
vector<int> st{
-1}; // 栈底:最后一个「无法匹配」的位置(哨兵)
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '(') {
st.push_back(i);
} else {
st.pop_back();
if (st.empty())
st.push_back(i); // 多余右括号,成为新分隔符
else
ans = max(ans, i - st.back());
}
}
return ans;
}
static int longestValidParenthesesDP(const string& s) {
const int n = (int)s.size();
vector<int> dp(n, 0); // dp[i]:以 s[i] 结尾的最长有效括号长度
int ans = 0;
for (int i = 1; i < n; ++i) {
if (s[i] != ')') continue;
if (s[i - 1] == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else {
int j = i - dp[i - 1] - 1; // 与 s[i] 配对的候选左括号位置
if (j >= 0 && s[j] == '(') dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
}
ans = max(ans, dp[i]);
}
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0032::Solution s;
CHECK_EQ(s.longestValidParentheses(")()())"), 4);
CHECK_EQ(s.longestValidParenthesesDP(")()())"), 4);
CHECK_EQ(s.longestValidParentheses(""), 0);
CHECK_EQ(s.longestValidParentheses("()"), 2);
CHECK_EQ(s.longestValidParentheses("(()"), 2);
CHECK_EQ(s.longestValidParentheses("()(()"), 2);
CHECK_EQ(s.longestValidParentheses("()(())"), 6);
CHECK_EQ(s.longestValidParenthesesDP("()(())"), 6);
CHECK_EQ(s.longestValidParentheses("(()(()"), 2); // 两段被夹住
CHECK_EQ(s.longestValidParenthesesDP("())((())"), 4);
CHECK_EQ(s.longestValidParentheses("())((())"), 4);