LeetCode 32. 最长有效括号

约 5 分钟
文章信息 22 个分类 3 个标签
分类
LeetCode CodeTop 困难 已解决 100-200 LeetCode 热题 100 腾讯 字节 阿里 华为 微软 美团 拼多多 小米 百度 网易 快手 滴滴 B站 虾皮 猿辅导 图森
标签
字符串 动态规划 栈

题目描述

✅ 32. 最长有效括号

image-20260928190710187

题意分析

给定一个只包含 '(' 和 ')' 的字符串，找出其中最长的连续有效括号子串，返回它的长度。有效子串要求左右括号能够完整匹配，且任意前缀的右括号数不超过左括号数。

子串必须连续，不能跳过中间的字符，也不能把分散的匹配对数相加。需要识别哪些位置会截断一段合法区间，以及当前匹配完成后，这段连续区间最早能从哪里开始。空字符串或没有有效子串时，答案为 0。

解法：栈维护未匹配下标

核心思路

[!blue]

有效括号子串一定以右括号结尾。扫描每个右括号时，只要能求出以当前位置结尾的最长有效长度，取所有位置中的最大值就是答案。栈除了用来匹配括号，还要保存下标，才能计算连续区间的长度。

栈底保存当前可匹配区域之前的边界：开始时放入 -1，表示字符串起点之前；之后如果遇到无法匹配的右括号，就把它的下标设为新边界。合法子串不能跨过这个失配位置。栈底之上保存尚未匹配的左括号下标，越靠栈顶，出现得越晚。

遇到左括号，直接将下标入栈。遇到右括号，先弹出栈顶：若原来有未匹配的左括号，这次弹出完成一对匹配，栈内至少还剩边界；若弹出后栈空，说明刚才弹掉的是边界，没有左括号可以配对，当前右括号必须成为新的边界，此时不能计算有效长度。

成功匹配后，设剩余栈顶下标为 b。它要么是最近一个仍未匹配的左括号，要么是栈底边界；它后面的字符到当前位置 i 已全部匹配，所以区间 [b + 1, i] 有效。这个区间不能再向左扩展，否则会包含一个尚未匹配的左括号或失配右括号。因此它正是以 i 结尾的最长有效子串，长度为 i - b。

已经匹配的下标会被弹出，因而后续相邻或嵌套的有效部分能够自然合并成更长区间。哨兵 -1 让从下标 0 开始的有效子串也能使用同一长度公式，无需额外分支。

解题步骤

  1. 初始化答案为 0，将哨兵 -1 入栈。
  2. 从左向右遍历下标 i；遇到 '(' 时将 i 入栈，继续处理下一个字符。
  3. 遇到 ')' 时弹栈。若弹出后栈空，将 i 入栈，作为后续有效区间不能跨越的新边界。
  4. 若弹出后栈非空，用 i - stack.peek() 更新最大长度。遍历结束后返回答案。

代码实现

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();

        // 起点之前的边界，使从下标零开始的有效段也能直接相减。
        stack.push(-1);
        int result = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
                continue;
            }

            stack.pop();

            // 当前右括号没有可配左括号，改记为新的失配边界。
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                // 剩余栈顶位于当前最长有效后缀之前，长度无需加一。
                result = Math.max(result, i - stack.peek());
            }
        }

        return result;
    }
}

func longestValidParentheses(s string) int {
    // 起点之前的边界，使从下标零开始的有效段也能直接相减。
    stack := []int{
        -1,
    }
    result := 0

    for i := range s {
        if s[i] == '(' {
            stack = append(stack, i)
            continue
        }

        stack = stack[:len(stack)-1]
        // 当前右括号没有可配左括号，改记为新的失配边界。
        if len(stack) == 0 {
            stack = append(stack, i)
        } else if length := i - stack[len(stack)-1]; length > result {
            // 剩余栈顶位于当前最长有效后缀之前，长度无需加一。
            result = length
        }
    }
    return result
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 为字符串长度。只遍历一次字符串，每个下标最多入栈、出栈各一次。
  • 空间复杂度：$O(n)$，最坏情况下字符串全为左括号，栈需要保存所有下标及哨兵。

关键点总结

[!green]

  • 栈底记录不可跨越的边界，其余位置记录尚未匹配的左括号；两类下标的作用不同。
  • 弹栈匹配之后再读栈顶，才能得到当前最长有效后缀之前的位置。
  • 每个右括号位置都计算一次可形成的最长有效后缀，覆盖了所有有效子串可能的结束位置。

易错点总结

[!yellow]

  • 弹栈后必须先判断是否为空，再读取栈顶；空栈时压入当前下标，才能建立新的边界并保证下一轮有可弹出的元素。
  • 长度使用弹栈后的栈顶计算，不能使用刚弹出的左括号下标，否则只能看到最近这一对，无法连接前面已匹配的部分。
  • b 是有效区间前一个位置，区间实际从 b + 1 开始，所以长度是 i - b，不再加 1；初始边界也必须为 -1。
  • 只统计匹配对数无法保证连续，必须通过未匹配下标确定有效区间的边界。

相似题目

题目 难度 关联与区别
20. 有效的括号 简单 匹配括号的基础语义相同，原题只判整串，本题还需记录下标或长度寻找最长合法段。
301. 删除无效的括号 困难 本题保留连续区间，原题可删除任意位置获得最长合法子序列式结果，目标不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/54637741
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！