通过最多执行 K 次加 1 操作，最大化相等元素子数组的长度

---

子数组是数组的连续部分，即可以将其视为另一个数组内部的数组。例如，取以下数组：

array[] = {1, 2, 3, 4, 5, 6}

对于上述数组，一个可能的子数组是

subarry[] = {2, 3, 4}

问题陈述

给定一个包含 N 个正整数的数组 arr[] 和一个表示可以添加到数组元素中的最大数字的正整数 K。任务是通过最多 K 次加 1 操作来递增数组的元素，并返回具有相同元素的最大可能子数组。

示例 1

Input: arr[] = {1, 2, 2, 3, 3, 3, 4}
K = 2
Output: 5

解释

• 将 arr[1] 加 1。然后 arr[1] = 3

• 将 arr[2] 加 1。然后 arr[2] = 3

• 因此，最终数组为 {1, 3, 3, 3, 3, 3, 4}。

在上述数组中，具有相同元素的最长子数组长度为 5。

示例 2

Input: arr[] = {1, 2, 4, 5, 2}
K = 5
Output: 3

解释

• 将 arr[1] 加 3。然后 arr[1] = 5

• 将 arr[2] 加 1。然后 arr[2] = 5

• 因此，最终数组为 {1, 5, 5, 5, 2}。

在上述数组中，具有相同元素的最长子数组长度为 3。

方法 1：滑动窗口 I

为了解决上述问题，第一步是对数组进行排序，然后执行二分搜索以选择具有相同元素的最大索引的值。然后，对于每个选定的元素，使用滑动窗口检查是否可以获得所有元素都相等的子数组。

示例：C++ 实现

在以下程序中，找到了最多 k 次递增的子数组的最大长度。

#include <bits/stdc++.h>
using namespace std;

// Function to check if subarray of length l exists having all elements equal
bool check(vector<int> vec, int l, int k, vector<int> arr){
   int i = 0;
   int j = l;
   while (j <= arr.size()){
      int maxSize = arr[j - 1];
      int total = maxSize * l;
      int curr = vec[j] - vec[i];
      if (curr + k >= total){
         return true;
      } else {
         i++;
         j++;
      }
   }
   return false;
}
// Function to find the maximum number of indices having equal elements after adding at most k numbers
int maxSubarray(vector<int> arr, int k){
   sort(arr.begin(), arr.end());
   vector<int> vec(arr.size());
   vec[1] = arr[0];
   for (int i = 1; i < vec.size() - 1; ++i){
   vec[i + 1] = vec[i] + arr[i];
   }
   int max = arr.size();
   int min = 1;
   int res = 1;
   while (min <= max){
      int mid = (max + min) / 2;
      if (check(vec, mid, k, arr)){
         res = mid;
         min = mid + 1;
      } else {
         max = mid - 1;
      }
   }
   return res;
}
int main(){
   vector<int> arr = {1, 2, 4, 5, 2};
   int k = 5;
   cout << (maxSubarray(arr, k));
   return 0;
}

输出

3

方法 2：滑动窗口 II

作为使用滑动窗口解决上述问题的第二个版本，我们将获取窗口，并对每个窗口找到最大元素以及使该窗口的所有元素相等所需的总操作次数。如果总操作次数小于 K，则递增，否则向右移动。重复上述步骤以获得最长子数组。

示例：C++ 实现

在以下程序中，找到了最多 k 次递增的子数组的最大长度。

#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum number of indices having equal elements
int maxSubarray(int arr[], int k, int n){
   int res = 0;
   int start = 0;
   long int s = 0;
   deque<int> dq;
   for (int i = 0; i < n; i++) {
      int a = arr[i];
      while (!dq.empty() && arr[dq.front()] <= a) {
         dq.pop_front();
      }
      dq.push_back(i);
      s += a;
      long int ops = (long int)arr[dq.front()] * (res + 1) - s;
      if (ops <= (long int)k)
      res++;
      else {
         if (dq.front() == start)
         dq.pop_front();
         s -= arr[start++];
      }
   }
   return res;
}
int main(){
   int arr[] = {1, 2, 4, 5, 2};
   int k = 5;
   int n = 5;
   cout << (maxSubarray(arr, k, n));
   return 0;
}

输出

3

结论

总之，讨论了两种解决给定问题的方法：

第一种方法使用滑动窗口查找具有相同元素的子数组。时间复杂度为 O(N*log(N))。

第二种方法使用滑动窗口和双端队列数据结构查找最大长度。时间复杂度为 O(N)。