LeetCode算法题(Go语言实现)_16

题目

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

一、代码实现

func longestOnes(nums []int, k int) int {left, zeroCnt, maxLen := 0, 0, 0for right := 0; right < len(nums); right++ {if nums[right] == 0 {zeroCnt++}// 窗口收缩条件for zeroCnt > k {if nums[left] == 0 {zeroCnt--}left++}// 更新最大窗口长度maxLen = max(maxLen, right - left + 1)}return maxLen
}func max(a, b int) int {if a > b { return a }return b
}

二、算法分析

1. 核心思路

• 滑动窗口机制：维护一个允许最多包含 k 个 0 的窗口，通过动态调整左右边界寻找最大连续 1 的区间
• 贪心策略：当窗口内 0 的数量超过 k 时，左边界右移直到满足条件，确保窗口始终包含有效解

2. 关键步骤

1. 初始化窗口：左边界 left=0，统计窗口内 0 的数量 zeroCnt
2. 扩展右边界：遍历数组元素，遇到 0 时增加计数
3. 收缩条件：当 zeroCnt > k 时，左移左边界并更新计数
4. 极值记录：每次循环记录窗口最大长度

3. 复杂度分析

指标	值	说明
时间复杂度	O(n)	每个元素最多被访问两次（左右指针各一次）
空间复杂度	O(1)	仅需存储指针和计数器变量

三、图解示例

四、边界条件与扩展

1. 特殊场景处理

• 全1数组：nums = [1,1,1], k=0 → 直接返回数组长度
• k=0情况：等价于寻找最长连续1的子数组
• 超大k值：当k ≥ 数组0的总数时返回数组长度

2. 多语言实现对比

语言	实现要点	性能优化技巧
Python	使用collections.deque记录0的位置	预计算0的索引数组加速窗口调整
Java	ArrayDeque存储0的索引，窗口调整时直接跳转到首个无效位置后	位运算优化0计数逻辑
C++	双指针配合zero_count变量，无需额外存储结构	循环展开优化边界判断

3. 算法对比

方法	优点	缺点
滑动窗口法	时间复杂度最优，空间效率高	需处理指针同步逻辑
前缀和+二分	支持随机查询	空间复杂度O(n)
暴力枚举	实现简单	时间复杂度O(n²)

五、总结与拓展

1. 核心创新点

• 窗口动态调整：通过zeroCnt计数器的状态机式管理，实现线性时间复杂度
• 无效位置跳跃：当窗口收缩时，左指针可直接跳转到首个无效0的后一位，减少冗余计算

2. 数学证明

设数组长度为 n，窗口左右指针移动总距离为 2n，算法时间复杂度严格为 O(n)。通过归纳法可证：每次窗口扩展必然覆盖当前最优解的可能性，收缩操作确保不遗漏更优解。

3. 应用场景扩展

• 网络质量监测：统计允许丢包情况下的最大连续正常信号段
• DNA序列分析：查找允许突变次数内的最长保守序列
• 用户行为分析：检测连续活跃天数（允许短暂中断）