1004. 最大连续1的个数 III Max Consecutive Ones III

问题描述

滑动窗口

这个问题跟之前的胡杨林补种一样, 用滑动窗口来解决:

• 窗口右侧经过0时, 计数加1
• 当窗口区间内的0的个数大于k 时, 把窗口左侧向右移, 直到窗口范围内的0的个数不大于k
• 然后更新最大的连续为1的个数

#![allow(unused)]
fn main() {
// 滑动窗口
pub fn longest_ones1(nums: Vec<i32>, k: i32) -> i32 {
    // 窗口右侧经过的0 的个数, 减去窗口左侧经过的0的个数, 就是需要翻转为1的个数

    let mut left = 0;
    let mut right = 0;
    let mut num_zero = 0;
    let k = k as usize;
    let mut longest_ones = 0;

    while right < nums.len() {
        // 需要翻转
        if nums[right] == 0 {
            num_zero += 1;
        }
        // 保证最大翻转次数不大于 k
        while num_zero > k {
            // 窗口左侧右移
            if nums[left] == 0 {
                num_zero -= 1;
            }
            left += 1;
        }

        // 注意边界情况.
        longest_ones = longest_ones.max(right - left + 1);

        // 窗口右侧向右移
        right += 1;
    }

    longest_ones as i32
}
}