Medium

题目描述

给定一个二进制数组 nums 和一个整数 k，如果可以最多翻转 k 个 0，则返回数组中连续 1 的最大个数。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

约束条件：

  • 1 <= nums.length <= 10^5
  • nums[i] 不是 0 就是 1
  • 0 <= k <= nums.length

解题思路

这是一个经典的滑动窗口问题。核心思路是维护一个窗口，其中最多包含 k 个 0。

算法思路：

  1. 滑动窗口法：使用双指针 left 和 right 维护一个窗口，该窗口内最多包含 k 个 0
  2. 窗口扩展：右指针不断右移扩展窗口，遇到 0 时计数器加 1
  3. 窗口收缩：当窗口内 0 的个数超过 k 时，左指针右移收缩窗口，直到窗口内 0 的个数不超过 k
  4. 记录最大值：在整个过程中记录窗口的最大长度

优化思路： 实际上我们不需要真正翻转数组中的 0，只需要统计窗口内 0 的个数即可。当窗口内 0 的个数不超过 k 时，这个窗口就是一个有效的连续 1 序列（经过翻转后）。

时间复杂度为 O(n)，因为每个元素最多被访问两次（一次被右指针访问，一次被左指针访问）。空间复杂度为 O(1)，只使用了常数个变量。

代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0;
        int zeroCount = 0;
        int maxLength = 0;
        
        while (right < nums.size()) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            
            maxLength = max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
};

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        zero_count = 0
        max_length = 0
        
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1
            
            while zero_count > k:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            
            max_length = max(max_length, right - left + 1)
        
        return max_length

public class Solution {
    public int LongestOnes(int[] nums, int k) {
        int left = 0, right = 0;
        int zeroCount = 0;
        int maxLength = 0;
        
        while (right < nums.Length) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            
            maxLength = Math.Max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

var longestOnes = function(nums, k) {
    let left = 0;
    let zeroCount = 0;
    let maxLength = 0;
    
    for (let right = 0; right < nums.length; right++) {
        if (nums[right]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 是数组 nums 的长度。每个元素最多被左右指针各访问一次，所以时间复杂度是线性的。只使用了常数个额外变量，空间复杂度为常数级别。

相关题目