Java二进制数组翻转0求最大连续1个数-滑动窗口详解

Java二进制数组翻转0求最大连续1个数 - 滑动窗口详解

问题描述

给定一个只包含0和1的二进制数组 nums 和一个整数 k，你可以翻转最多 k 个 0 为 1，返回数组中连续 1 的最大个数。

思路

可以使用滑动窗口解决这个问题。

1. 维护一个窗口: 窗口内最多包含 k 个 0。2. 窗口滑动: - 当窗口内 0 的个数超过 k 时，窗口左边界右移，直到窗口内 0 的个数小于等于 k。 - 每次移动窗口，更新最大连续 1 的长度。

代码实现javaclass Solution { public int longestOnes(int[] nums, int k) { int left = 0; int zeroCount = 0; int maxLen = 0; for (int right = 0; right < nums.length; right++) { if (nums[right] == 0) { zeroCount++; } while (zeroCount > k) { if (nums[left] == 0) { zeroCount--; } left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen; }}

复杂度分析

• 时间复杂度: O(n)，其中 n 是数组 nums 的长度，因为每个元素最多被访问两次。- 空间复杂度: O(1)，只使用了常数级别的额外空间。