【刷穿LeetCode】32. 最长有效括号

目录

一、题目描述

二、题目分析

2-1 栈-时间O(n) 空间O(n)

2-2 动态规划-时间O(n) 空间O(n)

三、Java代码

3-1 栈代码

3-2 动态规划代码

---

一、题目描述

给你一个只包含?'('?和?')'?的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i]?为?'('?或?')'

二、题目分析

看到括号匹配，条件反射就想到栈和动态规划，栈的特性可以很好的进行符号的抵消，动态规划可以将问题转化为子问题。

2-1 栈-时间O(n) 空间O(n)

栈可以入栈、出栈、对比栈顶，进行括号的抵消，对于本题，难点在于，如何记录有效子串的长度。

这里提供一个思路：遍历入栈，遇到i=）可以抵消时，先出栈，出栈后栈顶代表的下标，跟i的距离即为子串长度，模拟如下

字符串= "(()()"

【1】i=0=(? ? 入栈，栈=[0]

【2】i=1=(? ? 入栈，栈=[0,1]

【3】i=2=)? ? 栈顶为( ,出栈，栈=[0] ，子串长度为 i - 0 =2-0=2

【4】i=3=(， 入栈，栈=[0,3]

【5】i=4=)，?栈顶为( ,出栈，栈=[0] ，子串长度为 i - 0 =4-0=4

注意判断边界条件即可。

2-2 动态规划-时间O(n) 空间O(n)

F(n) 代表 从0-n长度的字符串中，最长有效括号的长度

第一个问题，有效长度什么时候会变动？

当且仅当遇到）时会进行变动。

第二个问题，当遇到）时，前面有什么可能的组合？

可能性是无限的，但是可以归纳为以下三种

【1】 ****( 即可以跟 n-1 匹配? ?长度+2

【2】(****? 即可以跟 n-k 匹配? ?长度+2

【3】****? ?即前面没有可匹配的

第三个问题，****是否以一个有效的字串结束？

【1】是，需要加上这个字串的长度

【2】否，无需操作

所以整体思路为：

当遇到）时，向前匹配，向前匹配的位置为

当为 ****( 时，pre为i-1

当为（**** 时，pre为 i-k-1

推理出状态方程如下：

注意边界条件即可。

注意：虽然时间复杂度都是O(n)，但是栈的操作会导致动态规划比较快。

三、Java代码

3-1 栈代码

7ms，超越10%用户

class Solution {

    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                   // 栈顶存在可以抵消的（
                if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') { 
                    stack.pop();
                    if (stack.isEmpty()) {
                        count = Math.max(count, i + 1);
                    } else {
                        // i到栈顶的距离 为 本串的最大长度
                        count = Math.max(count, i - stack.peek()); 
                    }
                    continue;
                }
            }
            stack.push(i);
        }
        return count;
    }

}

3-2 动态规划代码

0ms，超越100%用户

class Solution {
    // DP解法
    public int longestValidParentheses(String s) {
        if (s.length() <= 1)
            return 0;

        int[] dp = new int[s.length()];
        int max = 0;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') { // 向前匹配
                int pre = i - dp[i - 1] - 1; // 确定向前匹配的位置
                if (pre >= 0 && s.charAt(pre) == '(') {
                    dp[i] = dp[i - 1] + 2;
                    max = Math.max(dp[i], max);
                    if (pre > 0) {
                        dp[i] += dp[pre - 1];
                        max = Math.max(dp[i], max);
                    }
                }
            }
        }

        return max;
    }
}