題目連結:
題目意譯:
給定一個二元陣列 nums 以及一整數 k,回傳如果你能翻轉最多 k 個 0 的話陣列中最大的連續 1 之數量。
限制:
1 ≦ nums.length ≦ 10 ^ 5
nums[i] 只會是 0 或 1。
0 ≦ k ≦ nums.length
範例測資:
範例 1:
輸入: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
輸出: 6
解釋: [1,1,1,0,0,1,1,1,1,1,1]
粗體數字代表從 0 翻轉為 1。最長的子陣列以底線標示。
範例 2:
輸入: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
輸出: 10
解釋: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗體數字代表從 0 翻轉為 1。最長的子陣列以底線標示。
解題思維:
但是當我們遇到 0 的時候我們可以選擇將其變成 1(只要目前已操作數不為 k)。而我們可以看到這些操作應盡量聚在一起(也就是被變化的 0 應盡量靠近彼此)才能使連續 1 盡量地長。
當我們已經變過 k 個 0 為 1 時,此時可以把最久遠一次的操作取消掉,改為變化當前位置的 0。
然後看上述過程中最長的連續 1 之長度即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。