通过最多更改 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 是我们允许的更改次数。