leetcode括号匹配问题——32.最长有效括号

32.最长有效括号

题目描述：

 1、栈

 思路：首先看到括号，我们第一想法肯定是利用栈进行一个括号匹配，我们这道题也不例外；

我们先找到所有可以匹配的索引号，然后找出最长连续数列！

例如：s = )(()())，我们用栈可以找到，

位置 2 和位置 3 匹配，

位置 4 和位置 5 匹配，

位置 1 和位置 6 匹配，

这个数组为：2,3,4,5,1,6 这是通过栈找到的，我们按递增排序！1,2,3,4,5,6

找出该数组的最长连续数列的长度就是最长有效括号长度！

进入代码：

public int longestValidParentheses(String s) {
        if (s.length() < 2) return 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(')
                stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty())
                    stack.push(i);
                else
                    res = Math.max(res,i - stack.peek());
            }
        }
        return res;
    }

时间复杂度：O(n)

空间复杂度：O(1)

2、动态规划(空间换时间)

思路：当我们采用动态规划时，主要考虑几种情况：

当s.charAt(i) == '('时，dp[i] = 0;

反之s.charAt(i) == ')'时，我们又分：

      当s.charAt(i - 1) == '('时，dp[i] = dp[i - 2] + 2; 

      反之当s.charAt(i - 1) == ')'时,又分：

               当s.charAt(i - dp[i - 1] - 1) == '('时，dp[i] = dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2] 

                反之dp[i] = 0;

进入代码：

 public static int longestValidParentheses(String s) {
        if (s.length() < 2) return 0;
        int[] dp = new int[s.length()];
        //第一个符号无论如何长度都为0
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '(')
                dp[i] = 0;
            else
                if (s.charAt(i - 1) == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                } else {
                    if (i - dp[i - 1] -1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(')
                        dp[i] = i - dp[i - 1] - 2>=0
                                ? dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                                : dp[i - 1] + 2;
                    else dp[i] = 0;
                }
            max = Math.max(dp[i], max);
        }
        return max;
    }

时间复杂度：O(n)

空间复杂度：O(n)

总结：这是一道典型的括号匹配题，从栈到动态规划，用空间换时间，大家可以反复观看，一定要吃透！