题目分析
本题要求在最多翻转 K 个 0 的条件下,找到二进制数组中最长的连续 1 子数组。翻转操作实际上是将 0 视为可用资源,用来扩展连续 1 的区间。
解题思路
- 滑动窗口(双指针):
-
- 核心思想:维护一个窗口,确保窗口内最多包含 K 个 0(即最多可翻转 K 次)
- 右指针:遍历数组,扩展窗口
- 左指针:当窗口内 0 的数量超过 K 时,收缩窗口直到满足条件
- 关键操作:
-
- 遇到 0 时增加计数器
- 当 0 的数量超过 K 时,移动左指针直到移除一个 0
- 始终记录窗口的最大长度
完整代码
public class LeetCode1004 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
String[] strs = line.split(",");
int[] arr = new int[strs.length];
for (int i = 0; i < strs.length; i++) {
arr[i] = Integer.parseInt(strs[i]);
}
int k = Integer.parseInt(br.readLine().trim());
System.out.println(new Solution().longestOnes(arr, k));
}
static class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0; // 窗口左指针
int zeroCount = 0; // 当前窗口中0的数量
int maxLength = 0; // 记录最大窗口长度(即最大连续1的长度)
// 1. 右指针遍历数组
for (int right = 0; right < nums.length; right++) {
// 2. 遇到0时增加计数器
if (nums[right] == 0) {
zeroCount++;
}
// 3. 如果0的数量超过K,移动左指针直到移除一个0
while (zeroCount > k) {
if (nums[left] == 0) {
zeroCount--;
}
left++;
}
// 4. 更新最大窗口长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}
}
知识点分类
- 滑动窗口算法:
-
- 双指针维护可变大小窗口
- 时间复杂度 O(n),空间复杂度 O(1)
- 边界处理:
-
- 自动兼容 k=0 的特殊情况(相当于找原生连续1)
- 处理数组全为1的情况(此时 zeroCount 始终为0)
- 循环控制:
-
- 使用
while
确保窗口始终满足约束条件 - 右指针单向前进,左指针有条件前进
- 使用
- 问题转化技巧:
-
- 将"翻转操作"转化为"窗口内0的数量限制"
- 0 作为可消耗资源,1 作为目标元素