当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.032.Longest Valid Parentheses 最长有效括号

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


上一篇 LeetCode.044.Wildcard Matching 通配符匹配

下一篇 LeetCode.378.Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素

阅读
评论
875
阅读预计3分钟
创建日期 2020-07-04
修改日期 2020-07-04
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论