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

最长有效括号子串长度问题分析

问题描述

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

思路解析

为了找到最长的有效括号子串，可以使用栈来解决这个问题。栈的主要作用是记录左括号的位置，从而能够快速找到匹配的右括号。以下是具体的思路步骤：

代码实现

public class Solution {    public int longestValidParentheses(String s) {        if (s.empty()) {            return 0;        }        int maxLen = 0;        stack
   
     st = new stack<>(); // 栈中存储左括号的位置        st.push(-1); // 初始化栈，用于处理连续的右括号情况        for (int i = 0; i < s.size(); ++i) {            if (s.charAt(i) == '(') {                st.push(i); // 遇到左括号，压栈            } else {                st.pop(); // 遇到右括号，弹栈                if (st.empty()) { // 栈为空，说明当前右括号可能是一个单独的右括号                    st.push(i); // 为空则压栈，供后续计算使用                } else {                    int currentLen = i - st.top(); // 计算当前有效子串的长度                    maxLen = Math.max(maxLen, currentLen); // 更新最大长度                }            }        }        return maxLen;    }}
   

总结

通过上述方法，可以高效地找到字符串中的最长有效括号子串。这种方法的时间复杂度为O(n)，空间复杂度为O(n)，适用于处理较长字符串的情况。