LeetCode 32 Longest Valid Parentheses

    
        标签：
        
            LeetCode
        
            堆栈
        
    发布于：2021-05-22 15:11:27
    编辑于：2021-05-22 15:48:24
    浏览量：1372

题目分析

https://leetcode.com/problems/longest-valid-parentheses/

括号匹配问题，显然应该用堆栈，O(n) 时间复杂度，两次遍历。

第一次遍历字符串以构造堆栈，其内的值都是无法匹配的括号的序号；

第二次遍历堆栈，计算其内序号的最大间隔。

最后还要注意我们需要用字符串的长度和堆栈中保存的最后一个序号计算一次间隔。

4ms 的解法

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> stack;

        for(int i=0;i<s.size();i++) {
            char c = s[i];
            if(c=='(') {
                stack.push_back(i);
            } else {
                if(stack.empty() || s[stack.back()] == ')') {
                    // |), ))
                    stack.push_back(i);
                } else {
                    // ()
                    stack.pop_back();
                }
            }
        }
        int res = 0;
        int last = -1;
        for(int cur : stack) {
            res = max(res, cur - last - 1);
            last = cur;
        }
        res = max(res, int(s.size()) - last - 1);
        return res;
    }
};

0ms 的解法

这个是别人的解法，一次遍历解决问题。

关键在于这个 dp[n]，其存的值为 s[:n] 中以最后一个括号结尾的有效括号对长度。

如何构造 dp 中的值呢？两种情况（这两种情况下都要求当前符号为 )）：

当前符号与前一个括号匹配，即 s[i-1] == '('；
当前符号与更之前的括号匹配，此时要想匹配，这两个括号之间的所有括号必然已经匹配成功。结合前面 dp 的定义，则 dp[i-1] 就是这两个括号之间匹配括号长度。则 s[i - dp[i - 1] - 1] 就是我们要尝试匹配的那个括号。

这还没完，我们把这个匹配之后还需要加上更前面的匹配数，因为它们现在连在一起了。下面给了个例子：

()(()
()(())

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n <= 1) return 0;
        vector<int> dp(n);
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '('){
                    dp[i] = dp[i - 1] + 2;
                    if (i - dp[i - 1] - 2 >= 0) dp[i] += dp[i - dp[i - 1] - 2];
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

Links: leetcode-32-longest-valid-parentheses