题目

3499. 操作后最大活跃区段数 I

给你一个二进制字符串 s，其中：

  • '1' 表示一个活跃区段。
  • '0' 表示一个非活跃区段。

定义一次操作分为两个步骤：

  1. 选择一个两侧都是 '0' 的连续 '1' 区块，将其全部变为 '0'。
  2. 然后，选择一个两侧都是 '1' 的连续 '0' 区块，将其全部变为 '1'。

注意：处理时在 s 前、后各添加一个虚拟的 '1'（即等效字符串 t = '1' + s + '1'），两个虚拟 '1' 不计入最终结果。

你最多可以执行 一次 操作。请你计算并返回操作后活跃区段的最大数量。

示例 1：

1
2
3
输入：s = "01"
输出：1
解释：字符串中没有两侧都是 '0' 的 '1' 区块，无法执行操作。

示例 2：

1
2
3
4
5
6
7
输入：s = "0100"
输出：4
解释：
- 虚拟串 t = "1" + "0100" + "1" = "101001"
- 第一步：选择被 '0' 包围的 '1'（下标 2~3），将其变为 '0'。字符串变为 "100001"
- 第二步：选择合并后的大 '0' 区块（下标 1~4，两侧都是 '1'），将其变为 '1'。得到 "111111"
- 去掉两端虚拟 '1'，活跃区段数为 4（= 原有 1 个 '1' + 零块 1 + 零块 2）

示例 3：

1
2
3
输入：s = "1000100"
输出：7
解释：原始 1 的数量为 2，两个最大相邻零块的和为 3 + 2 = 5，结果为 2 + 5 = 7。

示例 4：

1
2
3
输入：s = "01010"
输出：4
解释：原始 1 的数量为 2，最大相邻零块和为 1 + 1 = 2，结果为 2 + 2 = 4。

提示：

  • 1 <= s.length <= 10^5
  • s[i] 为 '0' 或 '1'

思路

操作的本质：等价收益模型

这道题的难点在于阅读理解——需要将题目描述的操作转化为简洁的数学模型。

由于 s 两端各有一个 虚拟 '1' ，所以第一步”选择一个两侧都是 '0' 的 '1' 区块”是有可能发生的：两个虚拟 '1' 中间必须存在 '0' 才能形成有效操作。

一次完整操作的过程如下：

  1. 第一步：选中一块连续 '1'（前后紧邻 '0'），将其变为 '0'。此时，这块 '1' 前后的两个 '0' 区块被「打通」，合并为一个更大的 '0' 区块。
  2. 第二步：将合并后的大 '0' 区块（此时它的两侧都是 '1'）全部变为 '1'。

两步合在一起，净效果等价于：

选定两个相邻的 '0' 区块（中间至少隔有一个 '1' 区块），将它们全部变成 '1'。

中间那块 '1' 在第一步被变为 '0' 后，在第二步又被变了回来，因此实际上并没有损失。换言之：

1
操作带来的活跃区段增益 = 相邻两个零块的长度之和

最终答案就是：

1
答案 = 原始字符串中 '1' 的数量 + 最大相邻零块和

如果整串中零块数量不足 2 个（无法形成「两个相邻零块」），则无法执行有效操作，答案为原始 '1' 的数量。

举例分析

以 s = "1000100" 为例，我们给字符串加上虚拟 '1'：

1
2
3
虚拟串 t = "1" + "1000100" + "1" = "110001001"
          ↑                           ↑
        虚拟1                        虚拟1

零块分别为（只关注原始字符串部分）："000"（长度 3）和 "00"（长度 2），中间隔着一个 '1' 区块。

步骤 字符串状态 说明
初始化 110001001 虚拟串，加粗的是虚拟 '1'
第一步 100000001 将中间 '1' 变 '0'，两个零块合并为 "00000"
第二步 111111111 将合并零块变 '1'，中间 5 个变成 '1'

最终活跃区段增量 = 3 + 2 = 5。加上原有的 2 个 '1'，答案为 7。

算法设计

核心工作变为：找到所有零块，求相邻零块之和的最大值。

整体分三步：

  1. 统计原始字符串中 '1' 的总数，作为答案基数。
  2. 遍历字符串，提取所有连续 '0' 区块的长度。
  3. 遍历零块列表，求相邻两项之和的最大值，即为操作收益。若零块不足 2 个则收益为 0。

代码

基础版（两次遍历，O(n) 空间）

直观做法：第一遍统计 '1' 总数，第二遍提取零块长度存入列表，第三遍求相邻零块的最大和。

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
30
31
32
33
34
35
36
class Solution {
    public int maxActiveSectionsAfterTrade(String s) {
        int n = s.length();

        // 1. 统计原始 '1' 总数
        int cnt1 = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') cnt1++;
        }

        // 2. 分段提取所有零块长度
        List<Integer> zeroBlocks = new ArrayList<>();
        int i = 0;
        while (i < n) {
            int start = i;
            while (i < n && s.charAt(i) == s.charAt(start)) {
                i++;
            }
            if (s.charAt(start) == '0') {
                zeroBlocks.add(i - start);
            }
        }

        // 3. 零块不足 2 个，无法操作
        if (zeroBlocks.size() < 2) {
            return cnt1;
        }

        // 4. 求相邻零块的最大和
        int bestGain = 0;
        for (int j = 0; j < zeroBlocks.size() - 1; j++) {
            bestGain = Math.max(bestGain, zeroBlocks.get(j) + zeroBlocks.get(j + 1));
        }
        return cnt1 + bestGain;
    }
}

复杂度：时间 O(n)，空间 O(n)（零块列表最多存储 n 个元素）。

进阶版（一次遍历，O(1) 空间）

观察基础版：求相邻零块和时，每次只需要当前零块和上一个零块的长度，不需要保留全部列表。因此可以在分段遍历的同时，用 prevZero 记住上一个零块长度，边遍历边更新最大增益。

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
class Solution {
    public int maxActiveSectionsAfterTrade(String s) {
        int n = s.length();
        int ones = 0;          // 原始 '1' 的总数
        int maxGain = 0;       // 最大相邻零块和
        int prevZero = 0;      // 上一个零块的长度（0 表示尚未遇到零块）
        int runLen = 0;        // 当前连续段长度

        for (int i = 0; i < n; i++) {
            runLen++;
            // 字符变化或到达末尾 → 当前连续段结束
            if (i == n - 1 || s.charAt(i) != s.charAt(i + 1)) {
                if (s.charAt(i) == '1') {
                    ones += runLen;
                } else {
                    if (prevZero > 0) {
                        maxGain = Math.max(maxGain, prevZero + runLen);
                    }
                    prevZero = runLen;
                }
                runLen = 0;
            }
        }

        return ones + maxGain;
    }
}

变量说明：

变量 作用
ones 统计原始字符串中所有 '1' 的数量，作为答案的基数
maxGain 记录「相邻零块长度之和」的最大值，即操作能带来的最大增益
prevZero 上一个零块的长度。初始为 0，表示尚未遇到零块，顺带处理了「不足 2 个零块」的边界
runLen 当前连续相同字符段的长度计数器

复杂度：时间 O(n)，空间 O(1)。

遍历时采用「分段统计」技巧：当 s[i] != s[i+1] 或到达末尾时，[i - runLen + 1, i] 就是一个完整的同字符连续段，根据字符类型更新对应变量。

关键点

  1. 题意转化：理解「先消 '1' 再补 '0'」的两次操作等价于「直接把两个相邻零块变成 '1'」，中间 '1' 先删后补，互相抵消。这是本题最核心的洞察。
  2. 虚拟 '1' 的作用：保证两端的零块也能被”相邻 '1'“包围，从而使第二步操作合法。但虚拟位不计入答案。
  3. 不可操作的情况：当零块数量 < 2 时（prevZero 始终为 0），maxGain 保持为 0，答案即为原始 '1' 的总数。
  4. 一次遍历：利用分段统计的技巧，无需显式存储所有零块长度，只需保留 prevZero，将空间优化到 O(1)。

相关题目