透過最多更改 k 個 0 來形成的最長 1 子段（使用佇列）

---

在本文中，我們將找到可以透過最多更改 k 個 0 為 1 來形成的最長 1 子段。我們將使用佇列資料結構來解決此問題。

在這篇文章中討論的方法中，我們將使用佇列資料結構來查詢僅包含 1 的最長子陣列，該子陣列可以透過最多將 k 個 0 更改為 1 來形成。佇列資料結構將用於儲存先前出現的 0 元素的索引。每當我們遇到一個新的 0 時，我們將檢查佇列的大小。如果大小小於 k，那麼我們還可以將更多 0 轉換為 1。如果大小已經為 k，我們刪除新增的第一個 0，找出當前答案，並從佇列中刪除第一個 0。然後我們將當前 0 的索引新增到佇列中。我們重複此操作，直到到達陣列的末尾。之後，我們再次計算答案以應對最長子段在陣列末尾形成的極端情況。

問題陳述

給定一個大小為 N 的陣列，包含 0 和 1，我們需要找到如果允許將最多 k 個 0 更改為 1 則可以形成的最長子陣列或子段。

示例

輸入

arr = {1,0,1,0,1,0}, k=2

輸出

5

解釋

可能的解決方案之一是將索引 1 和 3 處的 0 更改為 1 以獲得以下陣列：{1,1,1,1,1,0}

因此，輸出為 5。

輸入

arr = {1,0,0,1,0,1}, k=4

輸出

6

解釋

我們可以將所有 0 更改為 1 以獲得陣列：{1,1,1,1,1,1}

因此，輸出將為 6。

輸入

arr = {0,0,1,0,1,1,0,1}, k=1

輸出

4

解釋

我們可以將索引 3 或 6 處的 0 更改為獲得陣列 {0,0,1,1,1,1,0,1} 或 {0,0,1,0,1,1,1,1}

在這兩種情況下，答案都將是 4。

方法

在這種方法中，我們將使用一種方法，該方法涉及利用佇列資料結構來識別僅由 1 組成的最長子陣列。可以透過將最多 k 個 0 轉換為 1 來獲得此子陣列。佇列將用於保留先前遇到的 0 元素的索引。在遇到新的 0 時，會檢查佇列的大小。如果大小小於 k，則有空間轉換其他 0。一旦大小達到 k，則刪除新增的第一個 0。此時，評估當前結果，並將初始 0 從佇列中刪除。隨後，將當前 0 的索引包含在佇列中。重複此過程，直到到達陣列的結尾。之後，重新計算結果以考慮最長子段在陣列末尾形成的情況。

演算法

• 步驟 1 - 初始化一個佇列資料結構。

• 步驟 1.1 - 使用 0 初始化三個整型變數，當前索引，我們可以不轉換超過 k 個 0 即可獲取的最低索引，結果。

• 步驟 2 - 迴圈直到當前索引小於陣列的大小

• 步驟 3 - 在每次迭代中

• 步驟 3.1 - 如果當前元素為 1，則轉到下一個元素。

• 步驟 3.2 - 如果當前元素為 0 且佇列的大小小於 k，則將當前索引新增到佇列中並轉到下一個元素。

• 步驟 3.3 - 如果當前元素為 1 且佇列的大小等於 k，則將結果更新為 result = max (result, current index − lowest index)，從佇列中彈出第一個元素並將最低索引更新為 1+第一個元素，最後將當前索引推入佇列。

• 步驟 4 - 迴圈結束後，再次更新結果以處理最長子段位於陣列末尾的情況。

• 步驟 5 - 返回結果。

示例

#include <bits/stdc++.h> 
using namespace std; 
int Longest_subsegment_of_ones(vector<int> &arr,int k) {
   queue<int> indices;
   int i=0, low=0;
   int res = 0;
   while(i<arr.size()){
      if(arr[i]==0){
         if(indices.size()==k){
            int x;
            if(k>0){
               x = indices.front();
               indices.pop();
            }
            else 
            x = i;
            res = max(res,i-low);
            low = x+1;
         }
         if(k>0)
         indices.push(i);
      }
      i++;
   }
   res = max(res,i-low);     
   return res;
} 
int main(){ 
   vector<int> arr = {0,0,1,0,1,1,0,1};
   int k = 1;
   cout<<Longest_subsegment_of_ones(arr,k)<<endl; 
   return 0; 
} 

輸出

4

時間複雜度 - O(N)，其中 N 是陣列中元素的數量。

空間複雜度 - O(k)，其中 k 是我們允許的更改次數。