力扣 Top100 32. 最长有效括号-CSDN博客

本文链接：https://blog.csdn.net/csdn_muxin/article/details/123600258

该博客讨论了如何利用栈数据结构解决LeetCode上的‘最长有效括号’问题。文章详细介绍了遍历字符串和使用栈来存储未匹配括号的索引的策略，以及如何在找到有效括号序列时更新最长长度。最后给出了Java代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode-cn.com/problems/longest-valid-parentheses/

大致题意：
给定一个由 ( 和 ) 组成的字符串，求出其中能构成有效括号的最长子串

思路

遍历字符串，使用栈存下所有还未匹配的左括号和右括号对应的索引，遍历规则为：

初始时，将 -1 入栈，作为标记待匹配的左括号索引和上次匹配失败的位置
若当前字符为左括号，将对应索引入栈
若当前字符为右括号，将栈顶元素出栈，若出栈后栈为空，则表示当前右括号之前没有可以匹配的左括号，将当前索引入栈，表示最近的还未匹配成功的右括号

那么可以知道未匹配的右括号之前不会有未匹配的左括号（若有，那么碰到右括号就会直接匹配），即未匹配的右括号都在栈底部

于是每次匹配成功后，就可以尝试更新最长有效括号子串

当前索引 - 栈顶元素值（上一个还未匹配成功的括号位置）即为当前匹配的有效括号串长度

代码：

	public int longestValidParentheses(String s) {
        // 队列中存入待匹配的左括号索引和上次匹配失败的位置
        Deque<Integer> stack = new ArrayDeque<>();
        int n = s.length();
        // 初始时放入 -1，表示上一个匹配失败的位置
        stack.offer(-1);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            // 左括号入栈
            if (ch == '(') {
                stack.offer(i);
            } else {
                int pos = stack.pollLast();
                // 栈为空，表示刚刚出栈的是上次匹配失败的位置，也就是不存在未匹配的左括号，更新当前位置上一次匹配失败的位置
                if (stack.isEmpty()) {
                    stack.offer(i);
                } else {    // 不为空，表示匹配成功
                    // 更新匹配成功的最长序列
                    ans = Math.max(i - stack.peekLast(), ans);
                }
            }
        }
        return ans;
    }