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

---