如何使用Java找出最长有效括号

在编程面试中，经常会遇到与字符串处理相关的问题。其中一个经典的问题是：如何找出字符串中最长的有效括号子串。有效括号子串是指由成对的括号组成的子串，且这些括号是正确匹配的。本文将详细介绍如何使用Java来解决这个问题，并提供相应的代码示例。

问题描述

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = ""
输出: 0

解题思路

要解决这个问题，我们可以使用动态规划或栈的方法。本文将重点介绍使用栈的解法，因为这种方法相对直观且易于理解。

使用栈的解法

栈是一种后进先出（LIFO）的数据结构，非常适合用来处理括号匹配的问题。我们可以通过栈来记录每个字符的索引，从而计算出最长的有效括号子串。

算法步骤

1. 初始化栈：我们首先在栈中压入一个初始值 -1，这样可以方便地计算有效括号的长度。
2. 遍历字符串：从左到右遍历字符串中的每个字符。
   • 如果当前字符是 '('，将其索引压入栈中。
   • 如果当前字符是 ')'，弹出栈顶元素。如果栈为空，说明当前 ')' 没有匹配的 '('，因此将当前索引压入栈中。否则，计算当前有效括号的长度，并更新最大长度。
3. 返回结果：遍历结束后，返回记录的最大长度。

代码实现

import java.util.Stack;

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 初始化栈

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i); // 压入当前索引
            } else {
                stack.pop(); // 弹出栈顶元素
                if (stack.isEmpty()) {
                    stack.push(i); // 如果栈为空，压入当前索引
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek()); // 计算当前有效括号长度
                }
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        LongestValidParentheses solution = new LongestValidParentheses();
        System.out.println(solution.longestValidParentheses("(()")); // 输出: 2
        System.out.println(solution.longestValidParentheses(")()())")); // 输出: 4
        System.out.println(solution.longestValidParentheses("")); // 输出: 0
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需要遍历字符串一次。
• 空间复杂度：O(n)，在最坏情况下，栈的大小可能达到 n。

动态规划解法（简要介绍）

除了栈的解法，我们还可以使用动态规划来解决这个问题。动态规划的思路是定义一个数组 dp，其中 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度。通过状态转移方程，我们可以逐步计算出每个位置的最长有效括号长度。

状态转移方程

• 如果 s[i] == ')' 且 s[i-1] == '('，则 dp[i] = dp[i-2] + 2。
• 如果 s[i] == ')' 且 s[i-1] == ')'，并且 s[i - dp[i-1] - 1] == '('，则 dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2。

代码实现

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length()];

        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;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        LongestValidParentheses solution = new LongestValidParentheses();
        System.out.println(solution.longestValidParentheses("(()")); // 输出: 2
        System.out.println(solution.longestValidParentheses(")()())")); // 输出: 4
        System.out.println(solution.longestValidParentheses("")); // 输出: 0
    }
}

总结

本文介绍了如何使用Java找出字符串中最长的有效括号子串。我们重点讲解了使用栈的解法，并简要介绍了动态规划的解法。栈的解法相对直观且易于实现，适合在面试中快速解决问题。希望本文能帮助你更好地理解和掌握这一经典算法问题。