[LeetCode] Longest Valid Parentheses 解题思路

时间:2022-01-25 04:00:52

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;