本文共 1271 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到给定只包含 '(' 和 ')' 的字符串中最长的有效括号子串的长度。有效括号子串指的是括号对正确匹配且连贯的子串。

方法思路

我们可以使用栈来解决这个问题。栈在处理括号匹配问题上非常有效。具体步骤如下：

这种方法确保在遇到每个可能的括号对时，能够正确计算其长度，并更新最大值。

解决代码

import java.util.Stack;public class Solution {    public int longestValidParentheses(String s) {        int maxAns = 0;        Stack
   
     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 {                    int currentLength = i - stack.peek();                    if (currentLength > maxAns) {                        maxAns = currentLength;                    }                }            }        }        return maxAns;    }}
   

代码解释

• 栈初始化：栈中初始存储-1，用于计算有效括号对的起始位置。
• 遍历字符串：逐个字符处理。
  • 遇到 '('，压入栈，记录当前位置。
  • 遇到 ')'，弹出栈顶元素。若栈为空，说明当前字符无法形成有效括号对，记录当前位置。否则，计算当前位置与栈顶元素的差值，更新最大有效括号长度。
• 返回结果：遍历结束后，返回最大有效括号长度。

这种方法高效且简洁，能够在 O(n) 时间复杂度内解决问题，适用于较长的字符串。