3499.操作后最大活跃区段数 I：一次遍历(脑筋急转弯)

【LetMeFly】3499.操作后最大活跃区段数 I：一次遍历(脑筋急转弯)

力扣题目链接：https://leetcode.cn/problems/maximize-active-section-with-trade-i/

给你一个长度为 n 的二进制字符串 s，其中：

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

你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：

• 将一个被 '0' 包围的连续 '1' 区块转换为全 '0'。
• 然后，将一个被 '1' 包围的连续 '0' 区块转换为全 '1'。

返回在执行最优操作后，s 中的 最大 活跃区段数。

注意：处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。

 

示例 1：

输入： s = "01"

输出： 1

解释：

因为没有被 '0' 包围的 '1' 区块，因此无法进行有效操作。最大活跃区段数为 1。

示例 2：

输入： s = "0100"

输出： 4

解释：

• 字符串 "0100" → 两端加上 '1' 后得到 "101001" 。
• 选择 "0100"，"101001" → "100001" → "111111" 。
• 最终的字符串去掉两端的 '1' 后为 "1111" 。最大活跃区段数为 4。

示例 3：

输入： s = "1000100"

输出： 7

解释：

• 字符串 "1000100" → 两端加上 '1' 后得到 "110001001" 。
• 选择 "000100"，"110001001" → "110000001" → "111111111"。
• 最终的字符串去掉两端的 '1' 后为 "1111111"。最大活跃区段数为 7。

示例 4：

输入： s = "01010"

输出： 4

解释：

• 字符串 "01010" → 两端加上 '1' 后得到 "1010101"。
• 选择 "010"，"1010101" → "1000101" → "1111101"。
• 最终的字符串去掉两端的 '1' 后为 "11110"。最大活跃区段数为 4。

 

提示：

• 1 <= n == s.length <= 105
• s[i] 仅包含 '0' 或 '1'

解题思路：脑筋急转弯

最终求的是1的个数而非连续1的个数，所以我们的目的是把尽可能多的0变成1。

首先可以把一段1变成0，这个操作的唯一意义就是把原本不相连的两段0连接起来，然后下一步一起变成1。

所以其实这道题最终是把相邻的两段0变成1，然后返回1的个数。也相当于返回原始1的个数加上相邻两段0中0的个数。

解题方法：一次遍历

回忆一下我们都需要哪些值：

1. 字符串中原始1的个数，这个可以由一个变量$cnt1$在一次遍历后得出。
2. 字符串中当前区段共计遍历到了多少个0，这个可以由一个变量$now_cnt0$在遍历过程中维护。当前字符是0的话$now_cnt0+1$；当前字符是刚刚由0转1的话，$now_cnt0$置$0$。
3. 字符串上一个连续0的个数，这个可以由一个变量$last_cnt0$来维护，初始值为无穷小。
4. 字符串最大两个连续0的个数，这个可以由一个变量$max0$来更新。

这样，我们就可以开始遍历字符串：

• 如果当前元素是0，则$now_cnt0+1$；
• 如果当前原始是刚刚由0变成了1，则更新$max0$、$last_cnt0$、$now_cnt0$。

时空复杂度分析

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-07-21 09:48:29
 */
class Solution {
public:
    int maxActiveSectionsAfterTrade(string& s) {
        int cnt1 = 0, max0 = -1000000;
        for (int last_cnt0 = -1000000, now_cnt0 = 0, i = 0, n = s.size(); i <= n; i++) {
            if (i < n && s[i] == '0') {
                now_cnt0++;
            } else if (i && s[i - 1] == '0') {  // 0->1
                max0 = max(max0, last_cnt0 + now_cnt0);
                last_cnt0 = now_cnt0;
                now_cnt0 = 0;
            }
            cnt1 += i < n && s[i] == '1';
        }
        return cnt1 + max(max0, 0);
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源