題目敘述
題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)和指定的k值。
我們最多可以把k個0反轉成1，請問連續為一的最長子陣列的長度是多少?
測試範例
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 <= 10^5
陣列nums的長度介於1~10^5之間。
nums[i]is either0or1.
陣列元素只有可能是0或1。
0 <= k <= nums.length
k值介於0~陣列nums的長度之間。
演算法
關鍵在於題目的要求是子陣列，而不是子序列。
子陣列一定要求必須連續。因此，最適合的演算法框架為滑動窗口sliding window。
題目說我們最多可以把k個0翻轉成1。
接著建立一個起始點從0開始的滑動窗口，依序從左向右滑動。
遇到1，right窗口右邊界直接往前延伸。
遇到0，假如k值還有剩餘，就把現在這個0翻轉成1。
假如k值已經<0，代表已經用完所有的反轉次數，這時候必須收縮窗口的左邊界left。
