算法核心解析
1. 问题转化:将"翻转1个1→0后求连续0段长度乘积的最小值"转化为O(n2)O(n^2)O(n2)的暴力搜索问题
2. 关键步骤:
* 枚举翻转位:遍历每个'1'位置进行临时翻转(第8-10行)
* 乘积计算:用双指针法统计连续0段长度(第13-22行)
* 极值维护:通过minx变量动态保持最小乘积(第25行)
3. 数学原理:乘积最小化需要尽可能使各段长度均衡(根据算术-几何平均不等式)
复杂度分析
* 时间复杂度:O(n2)O(n^2)O(n2)
* 外层循环:O(n)O(n)O(n)次遍历
* 内层扫描:每次O(n)O(n)O(n)的字符串遍历
* 空间复杂度:O(1)O(1)O(1)(仅用常数个辅助变量)
示例演算
以输入0000100010000001为例:
1. 翻转第5个字符'1'后得到0000000010000001:
* 连续0段:8个和6个 → 乘积48
2. 翻转第9个字符'1'后得到0000100000000001:
* 连续0段:4个和10个 → 乘积40(当前最小值)
3. 最终输出最小乘积40
边界情况处理
1. 全1字符串:题目保证至少存在1个0,无需处理
2. 超大结果:使用long long类型存储乘积(保证≤9×1018≤9×10^{18}≤9×1018)
3. 连续0段识别:通过else if(cnt>0)确保只有有效段被计算
该实现严格满足题目所有约束条件,并通过临时翻转→计算→恢复的"试探性"处理保证原始数据不被破坏。