LeetCode 1111. 有效括号的嵌套深度

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 2 个标签

分类

LeetCode 中等

题目描述

✅ 1111. 有效括号的嵌套深度

题意分析

将有效括号串的每个字符分到 A 或 B，两组都按原顺序组成有效子序列，并让两组最大嵌套深度中的较大值尽量小。子序列不必连续，返回每个字符的组号即可，组号零和一可以整体互换。

解法：按匹配括号的深度奇偶分组

核心思路

[!blue]

先看答案至少多大。设原串最大深度为 D，在达到这个深度的前缀处，未闭合左括号总数为 D。拆分后两组在同一前缀内的未闭合数量之和仍为 D，所以至少一组有 ceil(D / 2) 个，任何方案的最大深度都不可能小于这个下界。

为了达到下界，把原串中处于奇数嵌套层的整对括号放入一组，偶数层的整对放入另一组。扫描过程中，用 depth 记录尚未闭合的左括号数，也就是当前原串深度。

读到左括号时，它会新开一层，先让 depth 增一，再用 depth & 1 决定组号。读到右括号时，它关闭的正是当前这一层，所以先按现有 depth 分组，再减一。这样匹配的一对左右括号使用同一个层数，即使中间嵌套了其他括号，内部闭合后也会回到这个层数。

每一对都完整地保留在同一组，并维持原先左右顺序，因此右括号在本组中总能找到此前尚未闭合的匹配左括号，两组的任何前缀都不会出现右括号更多的情况。原串扫描完毕时所有括号都已配对，两组也各自闭合，所以都有效。

进一步看任意时刻：原串若有 d 个未闭合括号，它们的嵌套层恰好为 1..d。按奇偶分组后，两组分别留下 ceil(d / 2) 与 floor(d / 2) 个未闭合括号。因此两组的最大深度不超过 ceil(D / 2)，正好达到前面证明的下界。实现只需维护当前深度，无需先计算 D 或显式保存括号栈。

解题步骤

创建与输入等长的组号数组，初始化 depth = 0。

遇到左括号，先增加深度，再将深度奇偶写入当前位置。

遇到右括号，先写入当前深度奇偶，再减少深度。

扫描结束后返回组号数组，按组号各自取字符就得到两条有效子序列。

代码实现

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] group = new int[seq.length()];
        int depth = 0;

        for (int i = 0; i < seq.length(); i++) {
            if (seq.charAt(i) == '(') {
                depth++;
                group[i] = depth & 1;
            } else {
                group[i] = depth & 1;
                depth--;
            }
        }

        return group;
    }
}

func maxDepthAfterSplit(seq string) []int {
    group := make([]int, len(seq))
    depth := 0
    for i := range seq {
        if seq[i] == '(' {
            depth++
            group[i] = depth & 1
        } else {
            group[i] = depth & 1
            depth--
        }
    }
    return group
}

复杂度分析

时间复杂度：$O(n)$，每个括号处理一次。

空间复杂度：返回数组占 $O(n)$，除此之外只维护深度，额外空间为 $O(1)$。

关键点总结

[!green]

下界来自最深前缀中两组未闭合数量之和，无论如何分组都至少有一组承担一半。

同一匹配对按其嵌套层分组，保证两组独立有效。

奇偶层交替分配使任意前缀都尽量均衡，从而达到全局最优。

易错点总结

[!yellow]

不能直接按字符下标奇偶分组，字符位置不等于匹配括号的嵌套层。

左括号要先加深度，右括号要后减深度，否则同一对可能落入不同组。

返回的是每个原位置的组号，不是重新排列后的括号串，也不要求两组是连续子串。

相似题目

题目	难度	关联与区别
1614. 括号的最大嵌套深度	简单	复用括号深度计数；本题在每个深度上分组，而原题只需要取最大深度。
20. 有效的括号	简单	都要求匹配关系正确；只有一种括号时深度足够，多种括号还需要栈保存类型。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/58591707

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！