Given a string containing just the characters '('
and ')'
, find the length of the longest valid (well-formed) parentheses substring.
For "(()"
, the longest valid parentheses substring is "()"
, which has length = 2.
Another example is ")()())"
, where the longest valid parentheses substring is "()()"
, which has length = 4.
问题:求最长有效括号子字符串。
解题思路:
第一次做,以为是求整个字符串的有效括号长度是多少,思考了一会用 stack 可以求到,心想好像蛮简单的。扔到 LeetCode 跑了一下,结果错误,才发下原来是求 连续的最长有效括号长度。
重新理解题意后,开始做第二次。
想象括号匹配,就像玩那种 “天天爱消除” 新游戏,相邻两个字符,左边为 '(', 右边为 ')',则匹配成功,匹配成功的字符被替换为 '.'。
通过最多 n/2 次遍历,就可以把 s 中全部有效括号替换为 '.', 然后统计下连续 '.' 个数,就是题目的解,耗时 O(n*n)。实现后,扔到 LeetCode 上面,居然通过了,就是慢了一些。
再思考有没有更快的方法了,联想到第一次做用的 stack,可以借助 stack 一次遍历就将全部有效括号替换为 '.'。
第一步:一次遍历,stack 只存放 '(' 的下标。
当找到一个 '(',则压进 stack ;
当找到一个 ')',则把 stack.top 对于的字符替换为 '.',并弹出 stack.pop()。耗时O(n)。
第二步:求出连续 '.' 的最长长度, 耗时O(n)。
stack<int> sk; for (int i = ; i < s.size(); i++) {
if (s[i] == ')') {
if (sk.empty()) {
continue;
}else{
int idx = sk.top();
sk.pop();
s[idx] = marked;
s[i] = marked;
}
}else{
// s[i] is '(' sk.push(i);
}
} int len = ;
int maxL = ;
for (int i = ; i < s.size(); i++) {
if (s[i] == '.') {
len++;
}else{
maxL = max(maxL, len);
len = ;
}
}
maxL = max(maxL, len); return maxL;