LeetCode.032.Longest Valid Parentheses 最长有效括号

题目描述

32 Longest Valid Parentheses https://leetcode-cn.com/problems/longest-valid-parentheses/ 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

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

示例 2:

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

相似题目

LeetCode.020.Valid Parentheses 括号匹配 LeetCode.032.Longest Valid Parentheses 最长有效括号


解题过程

括号匹配的问题是典型的用栈解决的问题。 栈中存放数组下标,并保持栈顶是 “一个合法括号子串的前一个字符下标”,初始为 -1 遇到左括号直接将下标入栈。 遇到右括号时,栈顶要么是和当前右括号(即 s[i])匹配的左括号,要么是"一个合法括号子串的前一个字符下标" 将栈顶出栈,之后, 如果栈为空,说明当前合法子串结束,当前字符下标就是"一个合法括号子串的前一个字符下标" 如果栈不空,说明还在一个合法子串内,当前合法子串长度更新为"当前下标 减去 一个合法括号子串的前一个字符下标",并更新全局最大值

时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV202007 {
    public int longestValidParentheses(String s) {
        if (null == s || s.length() < 2) {
            return 0;
        }
        // 栈中存放的是数组下标
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1); // 栈顶是一个合法括号子串的前一个字符下标,初始为 -1
        int maxValidLength = 0; // 全局合法括号子串最大值
        for (int i = 0; i < s.length(); i++) {
            // 遇到左括号直接将下标入栈
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // 遇到右括号时,栈顶要么是和当前右括号(即 s[i])匹配的左括号,要么是"一个合法括号子串的前一个字符下标"
                stack.pop();
                if (stack.isEmpty()) {
                    // 如果栈为空,说明当前合法子串结束,当前字符下标就是"一个合法括号子串的前一个字符下标"
                    stack.push(i);
                } else {
                    // 栈不空,说明还在一个合法子串内,当前合法子串长度更新为"当前下标 减去 一个合法括号子串的前一个字符下标",并更新全局最大值
                    maxValidLength = Math.max(maxValidLength, i - stack.peek());
                }
            }
        }
        return maxValidLength;
    }
}

动态规划

dp[i] 表示以 s[i] 为结尾的最长有效括号的长度。 如果 s[i] 是左括号,则 dp[i] = 0 如果 s[i] 是右括号,分情况考虑: 1、如果 s[i-1] 是左括号,即 ...(),则正好可以和之前的有效括号子串接上,则 dp[i] = dp[i-2] + 2 2、如果 s[i-1] 是右括号,即 ...)),我们知道以 s[i-1] 为结尾的有效括号子串的长度是 dp[i-1],看这个子串的前一个字符: a) 如果存在且是 (,正好可以和当前右括号匹配,则以当前右括号为结尾的有效括号子串的长度等于 dp[i-1] + 2 + 他前面的有效子串长度,而 他前面的有效子串长度 = dp[i - dp[i-1] - 2],当然这个子串得存在才行,不存在就是 0 b) 如果不存在或不是 (,无法和当前右括号匹配,则以当前右括号为结尾的有效括号子串的长度等于 0


GitHub代码

algorithms/leetcode/leetcode/_032_LongestValidParentheses.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_032_LongestValidParentheses.java