1004. Max Consecutive Ones III (使用 C 語言解題)

1004. Max Consecutive Ones III

Solved

Medium

Topics

Companies

Hint

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

google 翻譯：

給定一個二進位數組 nums 和一個整數 k，如果最多可以翻轉 k 個 0，則傳回數組中連續 1 的最大數量。

想法一：

先用 right 把可以翻轉 0 的 k 個扣完，就是目前這時連續1的最大數量。
再加入 left +回翻轉個數，最後兩個差值就會是 1 的最大數量。

寫法一：

int longestOnes(int* nums, int size, int k) {
    int left = 0, right = 0;
    while(right < size) {
        if(nums[right++] == 0) // 移動 right
            k--;
        if(k < 0) { // k 沒了才需要移動 left
            if(nums[left++] == 0)
                k++;
        }
    }
    return right - left; // 差值即是連續 1 的最大數量
}

結果一：

還算不錯~ 後來試了幾種寫法效果都不好...

一開始參考的神人太厲害了~