A.每日一题：3499. 操作后最大活跃区段数 I

题目链接3499. 操作后最大活跃区段数 I中等算法原理解法贪心分块扫描60ms击败88.65%时间复杂度O(N)中译中求 连续0连续1连续0 的最大长度剩余1的个数这是1卧薪尝胆混入‘0’的圈子最后把身边所有0同化为‘1’并且集结所有剩余的’1‘的故事~~①将字符串 s 按连续相同字符划分成若干块记录每块的字符类型和长度②遍历所有块1.遇到 1 块将其长度累加到 total记录原始 1 的总数2.遇到 0 块若之前已经记录了一个 0 块的长度 pre则计算 pre 当前块长度并用它更新最大值 mx更新 pre 当前块长度保留该块长度供下一次相邻判断③最终答案 total mxJava代码class Solution { //3499. 操作后最大活跃区段数 I public int maxActiveSectionsAfterTrade(String S) { char[] sS.toCharArray(); //total原始字符串中所有1的总数 int total0; //mx所有相邻两个0段长度之和的最大值 int mx0; //pre0上一个0段的长度初始为极小值以便忽略第一个0段 int pre-0x3f3f3f3f; //cnt:当前正在扫描的连续相同字符块的长度 int cnt0; //遍历字符串按连续相同字符进行分段 for(int i0;is.length;i) { cnt;//当前块长度1 //如果到达字符串末尾或者当前字符与下一个字符不同说明当前块结束 if (is.length-1||s[i]!s[i1]) { //处理结束的块 if (s[i]1) { // 当前块是1块累加其长度到total totalcnt; }else { //当前块是0块计算它与前一个0块的长度之和 //precnt表示两个相邻0段长度之和尝试更新最大值 mxMath.max(mx,precnt); //更新pre为当前0块长度供下次使用 precnt; } //重置计数器开始记录下一个块 cnt0; } } //最终最大活跃区段数原始1总数最大相邻0段长度和 return totalmx; } }