)
【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。选择0100101001→100001→111111。最终的字符串去掉两端的1后为1111。最大活跃区段数为 4。示例 3输入s 1000100输出7解释字符串1000100→ 两端加上1后得到110001001。选择000100110001001→110000001→111111111。最终的字符串去掉两端的1后为1111111。最大活跃区段数为 7。示例 4输入s 01010输出4解释字符串01010→ 两端加上1后得到1010101。选择0101010101→1000101→1111101。最终的字符串去掉两端的1后为11110。最大活跃区段数为 4。提示1 n s.length 105s[i]仅包含0或1解题思路脑筋急转弯最终求的是1的个数而非连续1的个数所以我们的目的是把尽可能多的0变成1。首先可以把一段1变成0这个操作的唯一意义就是把原本不相连的两段0连接起来然后下一步一起变成1。所以其实这道题最终是把相邻的两段0变成1然后返回1的个数。也相当于返回原始1的个数加上相邻两段0中0的个数。解题方法一次遍历回忆一下我们都需要哪些值字符串中原始1的个数这个可以由一个变量c n t 1 cnt1cnt1在一次遍历后得出。字符串中当前区段共计遍历到了多少个0这个可以由一个变量n o w c n t 0 now_cnt0nowcnt0在遍历过程中维护。当前字符是0的话n o w c n t 0 1 now_cnt01nowcnt01当前字符是刚刚由0转1的话n o w c n t 0 now_cnt0nowcnt0置0 00。字符串上一个连续0的个数这个可以由一个变量l a s t c n t 0 last_cnt0lastcnt0来维护初始值为无穷小。字符串最大两个连续0的个数这个可以由一个变量m a x 0 max0max0来更新。这样我们就可以开始遍历字符串如果当前元素是0则n o w c n t 0 1 now_cnt01nowcnt01如果当前原始是刚刚由0变成了1则更新m a x 0 max0max0、l a s t c n t 0 last_cnt0lastcnt0、n o w c n t 0 now_cnt0nowcnt0。时空复杂度分析时间复杂度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(strings){intcnt10,max0-1000000;for(intlast_cnt0-1000000,now_cnt00,i0,ns.size();in;i){if(ins[i]0){now_cnt0;}elseif(is[i-1]0){// 0-1max0max(max0,last_cnt0now_cnt0);last_cnt0now_cnt0;now_cnt00;}cnt1ins[i]1;}returncnt1max(max0,0);}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
