【leetcode】32 最长有效括号（动态规划，栈）

题目链接：https://leetcode-cn.com/problems/longest-valid-parentheses/

题目描述

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

思路

1 暴力+栈

遍历每个长度为偶数的子串，判断字串是否为有效括号字符序列。
遍历字符串字符判断时维护一个栈：

• 每次遇到一个’(’，压栈；
• 如果遇到’)’，将栈顶元素弹出。如果栈空或者遍历完整个子字符串后栈中仍然有元素，那么该子字符串是无效的。

复杂度分析

• 时间复杂度：$O(n^3)$O(n3)。从长度为 N 的字符串产生所有可能的子字符串需要的时间复杂度为 $O(n^2)$O(n2) ) 。验证一个长度为 n 的子字符串需要的时间为 $O(n)$O(n) 。

• 空间复杂度：$O(n)$O(n)。子字符串的长度最多会需要一个深度为 n的栈。

运行超时 =,=!!!

/*
 * 栈+暴力
 * 时间复杂度O(n^2) 空间复杂度O(n)
 * 超时
 */
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        for (int i = 0; i < s.size(); ++i) {            // i为起始坐标
            for (int j = 2; j <= s.size() - i; j+=2) {  // j为长度
                if(isValid(s.substr(i,j)))
                    maxLen = max(maxLen, j);
            }
        }
        return maxLen;
    }
    bool isValid(string s){
        stack<char> stack1;
        for(auto ch:s){
            if(ch == '(')
                stack1.push('(');
            else if(stack1.empty()) // ) 匹配空栈
                return false;
            else
                stack1.pop();
        }
        return stack1.empty();
    }
};

2 栈+一次遍历

复杂度分析
时间复杂度：O（n）
空间复杂度：O（n）

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.size() < 2) return 0;
        int len = s.size();
        stack<int> st;      // 左括号元素的index
        st.push(-1);
        int maxLen = 0;
        for (int i = 0; i < len; ++i) {
            if(s[i] == '(')
                st.push(i);
            else{
                st.pop();
                if(st.empty())
                    st.push(i);
                else
                    maxLen = max(maxLen, i-st.top());
            }
        }
        return maxLen;
    }
};

3 动态规划