题目描述

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

示例 1:

输入: s = “(()” 输出: 2 解释: 最长有效括号子串是 “()”

示例 2:

输入: s = “)()())” 输出: 4 解释: 最长有效括号子串是 “()()”

示例 3:

输入: s = “” 输出: 0

解法分析

这道题要求我们找到给定字符串中最长的、格式正确的括号子串的长度。下面我们分析三种常见的解法：贪心算法、栈和动态规划。

解法一：贪心算法 (双指针扫描)

代码:

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int left = 0, right = 0, maxLen = 0;
        // 从左到右扫描
        for(int i = 0; i < n ; i++){
            char current = s.charAt(i);
            if(current == '('){
                left++;
            }else{
                right++;
            }
            if(left == right){ // 左右括号数相等，更新最大长度
                maxLen = Math.max(maxLen, 2 * right);
            }else if(right > left){ // 右括号数超过左括号数，当前子串无效，重置计数器
                left = 0;
                right = 0;
            }
        }
        // 重置计数器，从右到左扫描
        left = 0;
        right = 0;
        for(int i = n-1; i >= 0; i--){
            char current = s.charAt(i);
            if(current == ')'){
                right++;
            }else{
                left++;
            }
            if(left == right){ // 左右括号数相等，更新最大长度
                maxLen = Math.max(maxLen, 2 * left);
            }else if(left > right){ // 左括号数超过右括号数，当前子串无效，重置计数器
                left = 0;
                right = 0;
            }
        }
        return maxLen;
    }
}

思路分析:

核心思想是利用计数器 left 和 right 分别记录左右括号的数量。

1. 从左到右扫描:
   • 遍历字符串，遇到 ( 则 left++，遇到 ) 则 right++。
   • 当 left == right 时，意味着我们找到了一个有效括号子串（或者多个有效子串连接而成），其长度为 2 * right (或 2 * left)，我们更新 maxLen。
   • 当 right > left 时，说明右括号的数量超过了左括号，从当前扫描起点开始的子串不可能再构成有效括号了（因为缺少左括号来匹配多余的右括号），所以需要重置 left 和 right 为 0，相当于重新开始计数。
2. 为什么需要从右到左扫描?
   • 只进行从左到右扫描会漏掉一些情况。例如 s = "(()"，从左到右扫描时，left 最终会大于 right，left == right 的条件永远不会在扫描 ) 之后满足，导致计算出的 maxLen 为 0。但实际上 () 是一个长度为 2 的有效子串。
   • 从右到左扫描可以解决这个问题。它处理的是 left > right 的情况（即左括号过多）。遇到 ) 则 right++，遇到 ( 则 left++。当 left == right 时更新 maxLen。当 left > right 时（从右往左看，左括号数量超过了右括号），则重置计数器。
   • 通过结合两次扫描，我们可以覆盖所有可能的最长有效括号子串。

案例分析:

1. (s = "()((())")
   • 从左到右:
     • i=0, char='(': left=1, right=0.
     • i=1, char=')': left=1, right=1. left == right. maxLen = max(0, 2*1) = 2.
     • i=2, char='(': left=2, right=1.
     • i=3, char='(': left=3, right=1.
     • i=4, char='(': left=4, right=1.
     • i=5, char=')': left=4, right=2.
     • i=6, char=')': left=4, right=3.
     • 最终 left=4, right=3, maxLen=2.
   • 从右到左:
     • i=6, char=')': right=1, left=0.
     • i=5, char=')': right=2, left=0.
     • i=4, char='(': right=2, left=1.
     • i=3, char='(': right=2, left=2. left == right. maxLen = max(2, 2*2) = 4.
     • i=2, char='(': right=2, left=3. left > right. 重置 left=0, right=0.
     • i=1, char=')': right=1, left=0.
     • i=0, char='(': right=1, left=1. left == right. maxLen = max(4, 2*1) = 4.
     • 最终 maxLen = 4.
2. (s = "(()(")
   • 从左到右:
     • i=0, char='(': left=1, right=0.
     • i=1, char='(': left=2, right=0.
     • i=2, char=')': left=2, right=1.
     • i=3, char='(': left=3, right=1.
     • 最终 left=3, right=1, maxLen=0.
   • 从右到左:
     • i=3, char='(': right=0, left=1.
     • i=2, char=')': right=1, left=1. left == right. maxLen = max(0, 2*1) = 2.
     • i=1, char='(': right=1, left=2. left > right. 重置 left=0, right=0.
     • i=0, char='(': right=0, left=1.
     • 最终 maxLen = 2.

解法二：栈

代码:

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int longestValidParentheses(String s) {
       int n = s.length();
       // 栈底存储最后一个未匹配的')'的索引，或者-1表示边界
       Deque<Integer> stack = new ArrayDeque<>();
       stack.push(-1);
       int maxLen = 0;
       for(int i = 0; i < n; i++){
        char current = s.charAt(i);
        if(current == '('){ // 遇到左括号，将其索引入栈
            stack.push(i);
        } else { // 遇到右括号
            stack.pop(); // 尝试匹配栈顶的左括号
            if(stack.isEmpty()){ // 如果栈为空，说明当前右括号没有匹配的左括号
                stack.push(i); // 将当前右括号的索引作为新的"未匹配"边界入栈
            } else { // 如果栈不为空，说明匹配成功
                // 当前索引 i 减去 栈顶元素（上一个未匹配的')'或初始边界-1）的索引，得到当前有效长度
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
       }
       return maxLen;
    }
}

思路分析:

这种方法利用栈来维护可能构成有效括号的 ( 的索引。

1. 初始化: 栈中先放入一个 -1。这作为一个哨兵值，方便计算长度。它代表了有效括号子串开始之前的那个位置的索引。
2. 遍历字符串:
   • 遇到 (: 将其索引 i 压入栈中。
   • 遇到 ):
     • 首先弹出栈顶元素。这代表尝试用当前的 ) 去匹配最近的一个 (。
     • 如果弹出后栈为空: 说明当前的 ) 没有匹配的 (（之前的 ( 都已经被匹配完了，或者一开始就没有 (）。为了计算后续可能出现的有效括号长度，需要一个新的起点。我们将当前 ) 的索引 i 压入栈中，表示这个 ) 是下一个有效子串之前的”最后一个未匹配的右括号”的位置。
     • 如果弹出后栈不为空: 说明当前的 ) 找到了匹配的 (（刚刚被弹出的那个）。此时，栈顶的元素是上一个未能匹配的 ) 的索引（或者是初始的 -1）。当前索引 i 与栈顶索引 stack.peek() 之间的差值 i - stack.peek()，就是以当前 ) 结尾的最长有效括号子串的长度。我们用这个长度更新 maxLen。

案例分析 (s = ")()())")

• 初始化: stack = [-1], maxLen = 0
• i=0, char=')': pop() (弹出-1). 栈为空. push(0). stack = [0]. maxLen = 0.
• i=1, char='(': push(1). stack = [0, 1]. maxLen = 0.
• i=2, char=')': pop() (弹出1). 栈不为空. maxLen = max(0, i - stack.peek()) = max(0, 2 - 0) = 2. stack = [0].
• i=3, char='(': push(3). stack = [0, 3]. maxLen = 2.
• i=4, char=')': pop() (弹出3). 栈不为空. maxLen = max(2, i - stack.peek()) = max(2, 4 - 0) = 4. stack = [0].
• i=5, char=')': pop() (弹出0). 栈为空. push(5). stack = [5]. maxLen = 4.
• 循环结束，返回 maxLen = 4.

解法三：动态规划

代码:

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if(n < 2) return 0;
        // dp[i] 表示以索引 i 结尾的最长有效括号子串的长度
        int[] dp = new int[n];
        int maxLen = 0;
        for(int i = 1; i < n; i++){
           if(s.charAt(i) == ')'){ // 只有当结尾是')'时才可能构成有效子串
            if(s.charAt(i - 1) == '('){ // Case 1: "...()"
                // 长度等于 2 加上 i-2 结尾的最长有效长度
                dp[i] = (i-2 >= 0 ? dp[i-2] : 0) + 2;
            } else { // Case 2: "...))"
                // 查看 i-1 结尾的最长有效子串之前的那个字符
                int prevLen = dp[i-1]; // i-1 结尾的最长有效子串长度
                int potentialMatchIndex = i - prevLen - 1; // 潜在匹配的 '(' 的索引
                // 如果 prevLen > 0 (即 i-1 结尾的是有效子串) 且 潜在索引有效 且 该位置是'('
                if(prevLen > 0 && potentialMatchIndex >= 0 && s.charAt(potentialMatchIndex) == '('){
                    // 长度等于:
                    // 1. 以 i-1 结尾的子串长度 (dp[i-1])
                    // 2. 新匹配的这对括号长度 (+2)
                    // 3. 在 potentialMatchIndex 之前可能存在的有效子串长度 (dp[potentialMatchIndex - 1])
                    int beforePotentialLen = (potentialMatchIndex - 1 >= 0) ? dp[potentialMatchIndex - 1] : 0;
                    dp[i] = prevLen + 2 + beforePotentialLen;
                }
            }
            maxLen = Math.max(maxLen, dp[i]); // 更新全局最大长度
           }
           // 如果 s.charAt(i) == '('，dp[i] 默认为 0
        }
        return maxLen;
    }
}

思路分析:

动态规划的核心是定义状态和找到状态转移方程。

1. 状态定义: dp[i] 表示以索引 i 处的字符结尾的最长有效括号子串的长度。
2. 初始化: dp 数组所有元素初始化为 0。maxLen = 0。
3. 状态转移:
   • 如果 s[i] == '('，那么以 ( 结尾不可能构成有效括号子串，所以 dp[i] = 0。
   • 如果 s[i] == ')'，则需要考虑 s[i-1] 的情况：
     • Case 1: s[i-1] == '('
       • 此时 s[i-1] 和 s[i] 构成了一对 ()。
       • 这对比 () 可以接在以 i-2 结尾的最长有效子串后面。
       • 所以，dp[i] = dp[i-2] + 2。（需要处理 i-2 < 0 的边界情况，此时 dp[i-2] 视为 0）。
     • Case 2: s[i-1] == ')'
       • 这种情况形如 ...))。如果 s[i] 要构成有效括号，它必须匹配 s[i-1] 对应有效子串之前的那个 (。
       • 首先，我们需要知道以 i-1 结尾的最长有效子串长度，即 dp[i-1]。如果 dp[i-1] == 0，说明 s[i-1] 无法构成有效子串的结尾，那么 s[i] 也无法构成，dp[i]=0。
       • 如果 dp[i-1] > 0，则说明从 i - dp[i-1] 到 i-1 是一个有效子串。我们需要检查这个子串之前的那个字符，也就是索引为 potentialMatchIndex = i - dp[i-1] - 1 的字符。
       • 如果 potentialMatchIndex >= 0 且 s[potentialMatchIndex] == '('，那么这个 ( 就与当前的 s[i] == ')' 匹配了。
       • 匹配后的长度不仅包括了 dp[i-1] (内部的有效子串) 和新增的 2 (外层的 ( 和 s[i]))，还需要加上 potentialMatchIndex **之前**可能存在的有效子串的长度，即 dp[potentialMatchIndex - 1]。（同样需要处理 potentialMatchIndex - 1 < 0` 的边界）。
       • 所以，dp[i] = dp[i-1] + 2 + dp[potentialMatchIndex - 1]。
4. 结果: 遍历过程中，不断用 dp[i] 更新 maxLen。最终 maxLen 就是整个字符串中的最长有效括号子串长度。

案例分析 (s = "()(())")

• n=6, dp = [0, 0, 0, 0, 0, 0], maxLen = 0
• i=1, s[1]=')': s[0]=='(' (Case 1). dp[1] = (i-2<0?0:dp[-1]) + 2 = 0 + 2 = 2. maxLen = 2. dp = [0, 2, 0, 0, 0, 0].
• i=2, s[2]='(': dp[2] = 0. dp = [0, 2, 0, 0, 0, 0].
• i=3, s[3]='(': dp[3] = 0. dp = [0, 2, 0, 0, 0, 0].
• i=4, s[4]=')': s[3]=='(' (Case 1). dp[4] = (i-2>=0?dp[2]:0) + 2 = 0 + 2 = 2. maxLen = 2. dp = [0, 2, 0, 0, 2, 0].
• i=5, s[5]=')': s[4]==')' (Case 2).
  • prevLen = dp[4] = 2. prevLen > 0.
  • potentialMatchIndex = 5 - 2 - 1 = 2. potentialMatchIndex >= 0.
  • s[potentialMatchIndex] == s[2] == '('. Matches.
  • beforePotentialLen = (potentialMatchIndex - 1 >= 0 ? dp[potentialMatchIndex-1] : 0) = dp[1] = 2.
  • dp[5] = prevLen + 2 + beforePotentialLen = 2 + 2 + 2 = 6.
  • maxLen = max(2, 6) = 6. dp = [0, 2, 0, 0, 2, 6].
• 循环结束，返回 maxLen = 6.

方法比较与面试选择

优劣分析:

• 贪心算法:
  • 优点：空间复杂度最优，为 O(1)。
  • 缺点：思路相对巧妙，需要想到双向扫描来覆盖所有情况，解释其完备性可能需要多费些口舌。
• 栈:
  • 优点：思路相对直观，是处理括号匹配问题的经典方法，容易理解和实现。代码通常比较简洁。
  • 缺点：需要 O(n) 的额外空间存储栈。
• 动态规划:
  • 优点：是解决序列相关问题的通用强大方法，能体现 DP 思维能力。
  • 缺点：状态转移方程，特别是 s[i-1] == ')' 的情况，推导和边界处理相对复杂，容易出错。空间复杂度也是 O(n)。

面试选择建议:

在面试中，栈（解法二）通常是比较推荐和稳妥的选择。

• 原因:
  1. 普适性: 栈是解决括号匹配类问题的标准工具，面试官期望候选人掌握这种方法。
  2. 易于解释: 栈操作的逻辑（压入 ( 索引，遇到 ) 弹出匹配，计算长度）相对容易向面试官清晰地解释清楚。
  3. 不易出错: 相较于 DP 复杂的下标计算和边界判断，栈的实现逻辑更直接，在紧张的面试环境下更不容易写错。
• 其他选择:
  • 动态规划 (解法三): 如果你对 DP 非常自信，能够清晰地推导出状态转移方程并处理好边界情况，选择 DP 也是一个很好的选择，可以展示你扎实的 DP 功底。但如果感觉推导或解释起来有困难，不如选择更稳妥的栈。
  • 贪心算法 (解法一): 如果你能非常清晰地解释为什么双向扫描是必要且充分的，并且能快速写出 O(1) 空间的代码，这会是一个亮点（因为它空间最优）。但如果解释不清，可能会让面试官觉得思路不够严谨。

总结: 优先选择栈方法，因为它在思路清晰度、实现难度和面试考察频率之间取得了较好的平衡。如果对 DP 非常熟练，DP 也是优秀的选择。贪心法作为 O(1) 空间的解法，如果能讲清楚原理也是加分项。