透過最多 K 次遞增操作使元素相等的子陣列的最長長度


在這個問題中,我們將找到最長子陣列的長度,以便我們可以透過新增一些正整數的值來使所有子陣列元素相同,並且新增到每個元素的數字之和不應超過 K。

樸素的方法是找到在給定陣列的每個子陣列中使所有元素相同所需的成本。最後,考慮成本小於 K 且長度最大的子陣列的長度。

但是,我們將使用佇列資料結構來有效地解決這個問題。

問題陳述 - 我們給定一個包含整數的 N 個大小的陣列。此外,我們還給定一個正整數 K。任務是找到最長子陣列的長度,以便我們可以透過向子陣列的每個元素新增一些數字來使所有子陣列元素相同。此外,新增的數字之和不應超過 K。

示例

輸入

K = 6; arr[] = {2, 3, 5, 15, 3, 8};

輸出

3

解釋 - 我們可以取子陣列 {2, 3, 5}。因此,使子陣列所有元素相等的總成本是 {3, 2, 0} 的和,即 5。

輸入

K = 2; arr[] = {2, 2, 2, 2, 2, 2}

輸出

6

解釋 - 給定陣列的所有元素都相同。因此,我們可以選擇給定陣列作為子陣列。

輸入

K = 3; arr[] = {4, 5, 4, 4, 5, 1, 2, 3, 3, 3};

輸出

5

解釋 - 在這裡,我們可以選擇子陣列 {4, 5, 4, 4, 5} 或 {1, 2, 3, 3, 3},因為這兩個陣列具有相同的長度,並且使所有數字相等的成本都等於 3。

方法 1

在這種方法中,我們將遍歷給定陣列的所有子陣列。此外,我們將跟蹤當前子陣列的最大元素和元素之和。如果使子陣列所有元素相等的成本小於 K,並且其長度小於 max_len,我們將更新 max_len。

演算法

步驟 1 - 定義 max_len 並初始化為 0

步驟 2 - 使用迴圈開始遍歷陣列。在迴圈中,定義 maxEle 和 sum 變數,並將它們初始化為 0。

步驟 3 - 使用另一個巢狀迴圈從第 P 個索引遍歷陣列,因為子陣列從第 P 個索引開始。

步驟 4 - 如果它小於當前陣列元素,則更新 maxEle。此外,將陣列元素新增到“sum”變數。

步驟 5 - 現在,我們需要使子陣列的所有元素等於 maxEle,子陣列的長度為 q − p + 1。因此,如果 maxEle * (q − p + 1) 小於或等於 K,如果它小於 q − p + 1,則更新 max_len 變數。

步驟 6 - 返回 max_len 值。

示例

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

int maxSubArrayLength(int arr[], int N, int K) {
    int max_len = 0;
    // Traverse all subarrays of the given array
    for (int p = 0; p < N; p++) {
        int maxEle = 0;
        int sum = 0;
        for (int q = p; q < N; q++) {
            // Update maximum element
            maxEle = max(maxEle, arr[q]);
            sum += arr[q];
            // Check whether we can make all elements of the array equal to maxEle
            if (maxEle * (q - p + 1) <= sum + K) {
                // Update maximum length
                max_len = max(max_len, q - p + 1);
            }
        }
    }
    return max_len;
}
int main() { 
    int N = 6;
    int K = 6;
    int arr[] = {2, 3, 5, 15, 3, 8};
    cout << "The maximum length of subarray such that we can make all elements of it same is " << maxSubArrayLength(arr, N, K);
    return 0;
}

輸出

The maximum length of subarray such that we can make all elements of it same is 3

時間複雜度 - O(N*N),遍歷所有子陣列。

空間複雜度 - O(1)

方法 2

演算法

步驟 1 - 定義名為“maxQueue”的雙端佇列資料結構,用於儲存子陣列的最大元素的索引。

步驟 2 - 定義 pref_sum[] 陣列以儲存字首和,並將第 0 個索引初始化為 0。

步驟 3 - 遍歷陣列並將元素的字首和儲存到 pref_sum[] 陣列中。

步驟 4 - 將“left”和“max_len”初始化為 0,指向陣列的左索引並跟蹤子陣列的最大長度。此外,定義 max_ele 來儲存子陣列的最大元素。

步驟 5 - 再次開始遍歷陣列。

步驟 5.1 - 在 for 迴圈中,使用 while 迴圈從佇列中移除元素,直到佇列為空或佇列最後一個索引處的元素小於 arr[p]。

步驟 5.2 - 將 p 插入佇列。

步驟 5.3 - 如果 p 為 0,則將 max_ele 初始化為 arr[p]。否則,僅當它小於 arr[p] 時才更新 max_ele。

步驟 5.4 - 現在使用 while 迴圈進行迭代,直到 (p − left + 1) * max_ele − (pref_sum[p + 1] − pref_sum[left] 大於 K,或“left”點小於 p。

步驟 5.4.1 - 在 while 迴圈中,每次迭代將“left”遞增 1。

步驟 5.4.2 - 此外,刪除小於“left”的佇列元素。

步驟 5.5 - 如果它大於 max_len,則使用 p − left + 1 更新 max_len。

步驟 6 - 返回 max_len 值。

示例

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

int maxSubArrayLength(int arr[], int N, int K) {
    // Queue to store elements
    deque<int> maxQueue;
    // To store prefix sum
    int pref_sum[N + 1];
    pref_sum[0] = 0;
    // Calculating the prefix sum
    for (int p = 1; p <= N; p++) {
        pref_sum[p] = pref_sum[p - 1] + arr[p - 1];
    }
    // Start point of sub-array
    int left = 0;
    // For tracking the maximum element of the sub-array
    int max_ele;
    // To store the answer
    int max_len = 0;
    for (int p = 0; p < N; p++) {
        // Remove all smaller elements from the back to make the current element as maximum
        while (!maxQueue.empty() && arr[maxQueue.back()] < arr[p]) {
            maxQueue.pop_back();
        }
        // Insert current index
        maxQueue.push_back(p);
        // Update maximum element
        if (p == 0) {
            max_ele = arr[p];
        } else 
            max_ele = max(max_ele, arr[p]);
        // Calculating the cost to make all elements equal to the maximum
        while ((p - left + 1) * max_ele - (pref_sum[p + 1] - pref_sum[left]) > K && p > left) {
            // Increment starting point
            left++;
            // Remove the element from the current window
            while (!maxQueue.empty() && maxQueue.front() < left && left < p) {
                maxQueue.pop_front();
                max_ele = arr[maxQueue.front()];
            }
        }
        // Update maximum size
        max_len = max(max_len, p - left + 1);
    }
    return max_len;
}
int main() {
    int N = 6;
    int K = 6;
    int arr[] = {2, 3, 5, 15, 3, 8};
    cout << "The maximum length of subarray such that we can make all elements of it same is " << maxSubArrayLength(arr, N, K);
    return 0;
}

輸出

The maximum length of subarray such that we can make all elements of it same is 3

時間複雜度 - O(N^2),因為我們使用巢狀迴圈。

空間複雜度 - O(N),因為我們使用佇列。

在最壞情況下,兩種方法的時間複雜度相同。但是,當我們需要對常規陣列執行給定操作時,第二種方法更高效。

更新於:2023年8月2日

324 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始
廣告