[LeetCode 解題紀錄] 1004. Max Consecutive Ones III

1004. Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/

Problem:

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

題意

這題的題意是給定一個陣列 nums，陣列內只會有 0與 1 的數值，和一個整數 k，你最多可以將 k 個 0 翻轉成 1，要求返回陣列中可以得到的最多連續 1 的數量。

例如：

• 輸入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
• 解釋：可以翻轉兩個 0 成為 1，得到最多連續 1 的次數是 6。翻轉後的陣列可以是 [1,1,1,0,0,1,1,1,1,1,1]。

問題解析：

• 找對多連續的 1 數量，通常需要一個 count / window 來記錄
• 可以翻轉的 0 一定會是連續的，這樣才能創造出最大的連續 1
• 連續的 1 的數量會在每回合變動，紀錄最大值

解法

暴力解

這題如果用暴力解，必須要慮所有的子陣列，並計算每個子陣列中 0 的數量，檢查能否通過翻轉 0 的數量來得到連續的 1。

1. 遍歷所有可能的起點 start 和終點 end，生成所有可能的子陣列。
2. 對每個子陣列，計算其中 0 的數量。
3. 如果 0 的數量小於或等於 k，則更新最大連續 1 的長度。

這個方法需要遍歷所有的字陣列組合，再加上去計算每個子陣列中的 0 的數量，這個時間複雜度會是 O(n³)，這肯定不會是解法，只是這個思考方向是最直覺直接的，可以讓你在想題目的時候先整理一下思考邏輯。

使用 Sliding Window

Sliding Window 的基礎概念，就是透過不斷移動視窗的位置，來更新當下最佳的值，或是紀錄最終的答案。

Sliding Window 概念複習：

演算法筆記系列 — Two Pointer 與Sliding Window

1. 使用兩個指針 left 和 right 來表示滑動窗口。
2. 遍歷陣列時，用 count 記錄窗口內 0 的數量。
3. 如果 count 超過 k，移動 left 指針縮小窗口。
4. 每次移動 right 指針時，更新最大連續 1 的長度。

const longestOnes = (nums, k) => {
    let left = 0;
    let maxLength = 0;
    let count = 0;

    for (let right = 0; right < nums.length; right++) {
        // 當遇到 0 時，增加 count
        if (nums[right] === 0) {
            count++;
        }

        // 如果 count 超過 k，則移動 left 指針
        while (count > k) {
            if (nums[left] === 0) {
                count--;
            }
            left++;
        }

        // 更新最大長度
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

• 時間複雜度：O(n)
• 空間複雜度：O(1)

更多演算法與資料結構文章：

基礎演算法與資料結構學習筆記