付費限定文章

滑動窗口應用: 連續為一的最長子陣列_Leetcode #1004 精選75題

Marcel Eberle on Unsplash

題目敘述

題目會給定一個二元陣列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 either 0 or 1.

陣列元素只有可能是0或1。

• 0 <= k <= nums.length

k值介於0~陣列nums的長度之間。

演算法

關鍵在於題目的要求是子陣列，而不是子序列。

子陣列一定要求必須連續。因此，最適合的演算法框架為滑動窗口sliding window。

題目說我們最多可以把k個0翻轉成1。

接著建立一個起始點從0開始的滑動窗口，依序從左向右滑動。

遇到1，right窗口右邊界直接往前延伸。

遇到0，假如k值還有剩餘，就把現在這個0翻轉成1。

假如k值已經<0，代表已經用完所有的反轉次數，這時候必須收縮窗口的左邊界left。