leetcode热题HOT 32. 最长有效括号

一、问题描述：

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：
输入：s = “”
输出：0

二、栈：

1. 创建一个 Deque 类型的栈 stack 来存储左括号的索引位置，并初始化一个变量 result 用于记录最长有效括号子串的长度，以及一个临时变量 temp。
2. 将初始索引 -1 放入栈中，用于标记有效括号子串的起始位置。
3. 遍历输入字符串 s 中的每个字符：
   ①如果当前字符是左括号 ‘(’，将其索引位置压入栈中。
   ②如果当前字符是右括号 ‘)’，表示可能找到了一对匹配的括号。弹出栈顶元素，因为右括号与之匹配的左括号已经被消去：
   如果栈为空，说明没有与当前右括号匹配的左括号，将当前右括号的索引位置压入栈中，作为新的有效括号子串的起始位置。
   如果栈不为空，计算当前右括号与栈顶元素（上一个未匹配的左括号）之间的距离，更新 result 为较大值，以求得最长有效括号子串的长度。
   ③返回 result，即最长有效括号子串的长度。

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new LinkedList<Integer>(); // 使用栈来记录左括号的索引位置
        int result = 0, temp = 0; // 初始化最终结果和临时变量
        stack.push(-1); // 将一个初始索引 -1 放入栈中，用于标记有效括号子串的起始位置
        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 { // 如果栈不为空
                    result = Math.max(result, i - stack.peek()); // 更新最长有效括号子串的长度
                } 
            }
            //System.out.println(result);
        }
        return result; // 返回最长有效括号子串的长度
    }
}

• 时间复杂度分析：这段代码只需要一次遍历输入字符串 s，并且在每次遍历过程中，执行的操作都是常数时间复杂度的操作（如栈的压入、弹出、判断栈是否为空等）。因此，整体的时间复杂度为 (O(n))，n是输入字符串的长度。

三、动态规划：

1. 情况一：找到字符串形如 “……()”，找到（）的前一个位置，所以 dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
2. 情况二：找到字符串形如 “((……))”，找到子串“((……))” 前的第一个位置 i - dp[i - 1] - 2，所以 dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;

class Solution {
    public int longestValidParentheses(String s) {
        int result = 0; // 用于记录最长有效括号子串的长度
        int[] dp = new int[s.length() + 1]; // dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度
        dp[0] = 0; // 初始化，第 0 个字符的最长有效括号子串长度为 0
        // 从第一个字符开始遍历到倒数第二个字符
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') { // 当前字符为 ')'
                //情况一：字符串形如 “……()”
                if (s.charAt(i - 1) == '(') { // 前一个字符是 '('，形成了有效括号对 "()"
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; // 更新当前字符结尾的最长有效子串长度为前一个字符的最长子串长度加上 2
                } //情况二：字符串形如 “……))”
                else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { // 前一个字符是 ')'，并且其前面有有效括号子串
                    // 判断当前字符前面一个有效括号子串的前一个字符是否是 '('，如果是则更新当前字符结尾的最长有效括号子串长度
                    //i - dp[i - 1] - 2是子串“((……))”前的一个位置
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                result = Math.max(result, dp[i]); // 更新最长有效括号子串的长度
            }          
        }
        return result; // 返回最长有效括号子串的长度
    }
}

• 时间复杂度分析：O(n)，其中 n为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。