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：

输出：1

解释：

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

示例 2：

输出：4

解释：

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

示例 3：

输出：7

解释：

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

示例 4：

输出：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的个数，这个可以由一个变量c n t 1 cnt1cnt1在一次遍历后得出。
2. 字符串中当前区段共计遍历到了多少个0，这个可以由一个变量n o w c n t 0 now_cnt0nowc​nt0在遍历过程中维护。当前字符是0的话n o w c n t 0 + 1 now_cnt0+1nowc​nt0+1；当前字符是刚刚由0转1的话，n o w c n t 0 now_cnt0nowc​nt0置0 00。
3. 字符串上一个连续0的个数，这个可以由一个变量l a s t c n t 0 last_cnt0lastc​nt0来维护，初始值为无穷小。
4. 字符串最大两个连续0的个数，这个可以由一个变量m a x 0 max0max0来更新。

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

• 如果当前元素是0，则n o w c n t 0 + 1 now_cnt0+1nowc​nt0+1；
• 如果当前原始是刚刚由0变成了1，则更新m a x 0 max0max0、l a s t c n t 0 last_cnt0lastc​nt0、n o w c n t 0 now_cnt0nowc​nt0。

时空复杂度分析

• 时间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))
• 空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-07-21 09:48:29 */classSolution{public:intmaxActiveSectionsAfterTrade(string&s){intcnt1=0,max0=-1000000;for(intlast_cnt0=-1000000,now_cnt0=0,i=0,n=s.size();i<=n;i++){if(i<n&&s[i]=='0'){now_cnt0++;}elseif(i&&s[i-1]=='0'){// 0->1max0=max(max0,last_cnt0+now_cnt0);last_cnt0=now_cnt0;now_cnt0=0;}cnt1+=i<n&&s[i]=='1';}returncnt1+max(max0,0);}};

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

千篇源码题解已开源