透過最多執行 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)。