LeetCode 3499 操作后最大活跃区段数 I - Solution

1. 题目数据 (Problem Metadata)

• 题目类型：传统题
• 题目链接：3499. 操作后最大活跃区段数 I - 力扣（LeetCode）

2. 题意简述 (Problem Summary)

给定长度为 $n$（$1 \le n \le 10^5$）的二进制字符串 $s$，$s[i] \in \{\texttt{'0'}, \texttt{'1'}\}$。在 $s$ 两侧各补一个 $\texttt{'1'}$ 得到 $t = \texttt{'1'} + s + \texttt{'1'}$，最多执行一次「交易」：

1. 选一个被 $\texttt{'0'}$ 包围的连续 $\texttt{'1'}$ 块，整体变 $\texttt{'0'}$；
2. 再选一个被 $\texttt{'1'}$ 包围的连续 $\texttt{'0'}$ 块，整体变 $\texttt{'1'}$。

求操作后 $s$ 中 $\texttt{'1'}$ 的最大数量（两端补的 $\texttt{'1'}$ 不计入）。

3. 朴素解法 (Brute-Force)

最直接的思路是枚举每一步的选择：先枚举所有「被 0 包围的 1 块」作为第一步的目标，变 0 后再枚举所有「被 1 包围的 0 块」作为第二步的目标，统计最终 1 的个数取最大。

字符串分段数为 $O(n)$，两步枚举组合数为 $O(n^2)$，每步重新计数 $O(n)$，总复杂度 $O(n^3)$。$n = 10^5$ 时约 $10^{15}$ 次运算，远超时限。瓶颈在于重复统计 1 的个数——其实操作对 1 总数的影响是可解析计算的，无需模拟。

4. 核心解法 (Main Solution)

特殊性质

交易的两步是耦合的：第一步把某个 1 块变 0，会让它两侧的 0 块合并成一个更大的 0 块；第二步再把这个合并后的 0 块变 1。关键在于，合并后的 0 块是否仍被 1 包围——答案是肯定的，因为原 1 块两侧的 0 块外侧本来就是 1。

关键突破

把操作还原到 $t$ 的分段结构上。设选中的 1 块为 $B_1$，其左右两侧的 0 块为 $L_0$、$R_0$，则第一步后 $L_0 + B_1 + R_0$ 合并成一个大 0 块（长度 $|L_0| + |B_1| + |R_0|$），两侧仍是 1，满足第二步的条件。第二步将其变 1 后，净效果是

$$\underbrace{L_0}_{\texttt{0}}\ \underbrace{B_1}_{\texttt{1}}\ \underbrace{R_0}_{\texttt{0}} \longrightarrow \underbrace{L_0 + B_1 + R_0}_{\texttt{1}}$$

增量 $= |L_0| + |R_0|$（$B_1$ 本来就是 1，变 1 无增量；$L_0$、$R_0$ 从 0 变 1，每个位置贡献 $+1$）。也就是说，一次交易的本质是「选两个相邻的、被 1 包围的 0 块，把它们连同中间的 1 块一起变成 1」，增量恰为两个 0 块长度之和。

推导过程

将 $t$ 按连续相同字符分段，得到交替的 1 段与 0 段。筛选出所有「被 1 包围的 0 段」，按出现顺序记其长度为 $z_1, z_2, \dots, z_k$。两个 0 段「相邻」指它们之间只隔一个 1 段（即可被同一笔交易所合并）。则

$$\text{ans} = \text{cnt1} + \max_{1 \le i < k}\big(z_i + z_{i+1}\big)$$

其中 $\text{cnt1} = s.\text{count}(\texttt{'1'})$ 为不操作时的 1 总数。若 $k < 2$（没有两个相邻的可合并 0 段），则无法交易，$\text{ans} = \text{cnt1}$。

5. 正确性证明 (Proof of Correctness)

需证两点：交易增量公式成立，且枚举相邻 0 段对不重不漏。

增量公式。设交易选中 1 段 $B_1$，其左右 0 段为 $L_0$、$R_0$。第一步 $B_1 \to \texttt{0}$，1 总数减少 $|B_1|$；此时 $L_0, B_1, R_0$ 合并为一个 0 段，被 1 包围，第二步整体变 1，1 总数增加 $|L_0| + |B_1| + |R_0|$。净增量 $= (|L_0| + |B_1| + |R_0|) - |B_1| = |L_0| + |R_0|$。公式成立。

不重不漏。$t$ 的分段交替排列，任意被 1 包围的 0 段其两侧必为 1 段。一个可交易的 1 段必须两侧紧邻 0 段，故它恰对应「左右两个 0 段」这一对。遍历所有相邻的 0 段对 $(z_i, z_{i+1})$，即覆盖所有可交易 1 段，且不同 1 段对应不同的 0 段对，不重不漏。

综上所述，枚举相邻 0 段对取 $z_i + z_{i+1}$ 最大值，加上 $\text{cnt1}$，即为最优解。

6. 复杂度分析 (Complexity)

• 时间复杂度：$O(n)$。分段遍历一次，筛选与求相邻最大和各一遍，均为线性。$n = 10^5$ 时约 $3 \times 10^5$ 次运算，轻松通过。
• 空间复杂度：$O(n)$，存储分段列表与筛选结果。远低于典型内存限制。
• 常数优化：可用一次遍历维护「上一个被 1 包围的 0 段长度 $\text{pre}$」与「相邻和最大值 $\text{mx}$」，将空间降至 $O(1)$。但 $O(n)$ 已足够，分段写法可读性更好，不必为省内存引入额外状态维护。$O(1)$ 写法见 §9。

7. 实现细节与避坑指南 (Implementation Details)

8. 参考代码 (Reference Code)

下面是我提交时使用的版本，采用「分段 + 筛选被 1 包围的 0 段 + 取相邻对最大值」的思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        n = len(s)

        # 按连续相同字符分段，首部插入虚拟 1 段
        chunks = [("1", 1)]
        tpe, lth = s[0], 1
        for i in range(1, n):
            if s[i] != s[i - 1]:
                chunks.append((tpe, lth))
                tpe, lth = s[i], 1
            else:
                lth += 1
        chunks.append((tpe, lth))   # 尾段
        chunks.append(("1", 1))      # 末尾虚拟 1 段

        # 筛选被 1 包围的 0 段长度
        zeros = [
            chunks[i][1]
            for i in range(1, len(chunks))
            if chunks[i][0] == "0"
            and chunks[i - 1][0] == "1"
            and chunks[i + 1][0] == "1"
        ]

        cnt1 = s.count("1")
        # 取相邻两个 0 段长度之和的最大值，加到 cnt1 上
        return max([cnt1] + [cnt1 + zeros[i] + zeros[i + 1]
                             for i in range(len(zeros) - 1)])

9. 补充说明 (Additional Notes)

• 题目背景：本题出自 LeetCode 第 153 场双周赛，题面用「交易」包装了一次区间翻转操作，核心是识别出两步操作的净效果等价于「合并两个相邻 0 段」。这种「把连续操作归约为单次效果」的化简思路在字符串贪心题中很常见。
  0
• 与 3501 题的关系：本题是 I 版（$n \le 10^5$），同系列的 II 版（3501）将 $n$ 放大到 $10^5$ 的多次操作，思路一脉相承但需更精细的维护。

其他版本

下面是一次遍历的 $O(1)$ 空间写法，省去分段存储，边读边维护「上一个 0 段长度」与「相邻和最大值」：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        n = len(s)
        cnt1 = 0          # 1 的总数
        pre = -1          # 上一个被 1 包围的 0 段长度，-1 表示尚不存在
        mx = 0            # 相邻两个 0 段长度之和的最大值
        i = 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cur = j - i
            if s[i] == "1":
                cnt1 += cur
            else:
                if pre != -1:
                    mx = max(mx, pre + cur)
                pre = cur
            i = j
        return cnt1 + mx

两种写法复杂度同为 $O(n)$，差异在空间与可读性：分段写法逻辑分层清晰，便于调试和理解；一次遍历写法空间更省、常数更小。思路都经典，都有学习的价值。