🔗 🟡 2779. Maximum Beauty of an Array After Applying Operation 1638

tags: `Weekly Contest 354` `滑動窗口(Sliding Window)` `排序(Sorting)` `前綴和(Prefix Sum)` `差分陣列(Difference Array)`

題意

給定一個下標從 $0$ 開始的整數陣列 $\text{nums}$ 和一個非負整數 $k$ 。

在每一次操作中，你可以執行以下操作：

在範圍 $[0, \text{nums.length} - 1]$ 中選擇一個 此前沒有選過 的下標 $i$ 。
將 $\text{nums}[i]$ 替換成範圍在 $[\text{nums}[i] - k, \text{nums}[i] + k]$ 內的任一整數。

返回在執行任意次操作後，陣列 $\text{nums}$ 的相同元素子序列的最大長度。

注意：你只能對每個下標執行一次操作。

約束條件

$1 \leq \text{nums.length} \leq 10^5$
$0 \leq \text{nums[i]}, k \leq 10^5$

思路

方法一：排序(Sorting) + 滑動窗口(Sliding Window)

首先轉換問題，由於任何一個數 $\text{nums}[i]$ ，都能轉換為 $[\text{nums}[i]-k, \text{nums}[i]+k]$ 中的任意一個數，因此對於任意一個數 $x$ ，與其能變成相同數字 $y$ 的數皆會落在 $[x-2k, x]$ 或 $[x, x+2k]$ 中。

換句話說，若 $\text{nums}$ 中的某個子序列可以透過操作構成相同元素子序列，則子序列中的最大數 $mx$ 和最小數 $mn$ 之差不會超過 $2k$ 。因此可以使用滑動窗口(Sliding Window) 的方法來求解，維護一個窗口，其中窗口內的最大值和最小值之差不超過 $2k$ 。

為了確保窗口的正確和有序，可以對 $\text{nums}$ 陣列進行排序，由小到大枚舉元素。使用一個左指針 $left$ 記錄窗口左端點，並在枚舉右端點 $right$ 的過程中，不斷更新左指針 $left$ ，確保窗口內的元素值差不超過 $2k$ 。之後以當前窗口大小並更新答案，最後返回答案即可。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，排序需要 $\mathcal{O}(n \log n)$ 的時間，枚舉右端點需要 $\mathcal{O}(n)$ 的時間。
空間複雜度： $\mathcal{O}(1)$ ，忽略排序所需的空間。

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans, left = 0, 0
        for right, x in enumerate(nums): # 枚舉右端點
            while x - nums[left] > k * 2: # 保證窗口內最大值和最小值之差不超過2k
                left += 1
            ans = max(ans, right - left + 1) # 更新答案
        return ans

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = 0, left = 0;
        for (int right = 0; right < n; right++) { // 枚舉右端點
            while (nums[right] - nums[left] > k * 2) { // 保證窗口內最大值和最小值之差不超過2k
                left++;
            }
            ans = max(ans, right - left + 1); // 更新答案
        }
        return ans;
    }
};

方法二：前綴和(Prefix Sum) + 差分陣列(Difference Array)

再來是一個比較直覺的思路，對於 $\text{nums}$ 中的每個數 $x$ ，其能轉換成相同數字的範圍為 $[x-k, x+k]$ ，因此可以對 $\text{nums}$ 中的每個數 $x$ ，在 $[x-k, x+k]$ 區間上 $+1$ 。對於值域中的每個數字 $i$ ，其出現的次數為 $\text{nums}$ 中能轉換成 $i$ 的數字的個數，即為將所有元素轉換為 $i$ 的子序列之最大長度。

但是這個思路需要使用到區間加法，若枚舉 $[x-k, x+k]$ 區間上的每個數字 $i$ ，對其出現次數進行加法操作，則在最壞情況下，對於每個數字 $x$ ，可能都要進行值域大小 $M$ 次的加法操作，因此時間複雜度為 $\mathcal{O}(nM)$ ，其中 $M$ 是值域的大小。

因此需要引入差分陣列(Difference Array) ，這是一個與前綴和(Prefix Sum) 相對應的概念，可以在 $O(1)$ 的時間實現區間加法的功能，將區間 $[l, r]$ 上的所有數 $+1$ 可以轉換成對差分陣列的 $l$ 位置 $+1$ ， $r+1$ 位置 $-1$ ，最後再對差分陣列做前綴和即可還原出原始陣列。差分陣列的具體介紹本處省略，可以自行參考相關資料。

對於 $\text{nums}$ 中的每個數 $x$ ，在 $[x-k, x+k]$ 區間上 $+1$ ，可以對應到差分陣列中的 $x-k$ 處 $+1$ ， $x+k+1$ 處 $-1$ 。之後對差分陣列做前綴和，即可得到一個新的陣列 $s$ ，其中 $s[i]$ 表示在 $i$ 位置上的數字在 $\text{nums}$ 中出現的次數。

依照上述操作，會產生負數值域，需要做偏移處理或使用雜湊表來處理負數值域。但可以注意到，比最小值 $mn$ 更小的值域和比最大值 $mx$ 更大的值域不會對答案有影響，因此可以轉換成在 $[max(x-k, 0), min(x+k, mx)]$ 區間上 $+1$ ，其中 $mx$ 是 $\text{nums}$ 中的最大值，而根據約束條件 $0 \leq \text{nums[i]} \leq 10^5$ ，因此 $0 \leq mn$ ，即可以將 $mn$ 視為 $0$ ，如此便不用處理值域的偏移問題。

此外還需要注意，因為對區間 $[0, mx]$ 做區間加法，需要使用到差分陣列中的 $mx+1$ 位置，因此差分陣列的長度需為 $mx+2$ 。而在還原成原始陣列時，可以對差分陣列做前綴和，其中前綴和陣列的長度為 $mx+3$ ，但可以優化成常數空間，只需維護一個變數 $s$ 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n + m)$ $O (n + m)$ ，其中 $n$ $n$ 是陣列 $\text{nums}$ $nums$ 的長度， $m$ $m$ 是陣列中的最大值。
- 遍歷陣列 $\text{nums}$ 需要 $\mathcal{O}(n)$ 的時間。
- 遍歷差分陣列需要 $\mathcal{O}(m)$ 的時間。
空間複雜度： $\mathcal{O}(m)$ $O (m)$ 。
- 差分陣列的長度為 $m+2$ 。
- 前綴和陣列的長度為 $m+3$ ，但可以優化成常數空間，見 C++ 的範例程式碼。

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        diff = [0] * (mx + 2)
        for x in nums:  # 在 [x-k, x+k] 區間上 +1
            diff[max(x - k, 0)] += 1
            diff[min(x + k + 1, mx + 1)] -= 1
        s = [0] * (mx + 3)  # 對 diff 做前綴和，可優化成常數空間
        for i in range(1, mx + 3):
            s[i] = s[i - 1] + diff[i - 1]
        return max(s)

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int mx = *max_element(nums.begin(), nums.end());
        vector<int> diff(mx + 2);
        for (int x : nums) {
            diff[max(x - k, 0)]++;
            diff[min(x + k + 1, mx + 1)]--;
        }
        int ans = 0, s = 0;
        for (int x : diff) {
            s += x;
            ans = max(ans, s);
        }
        return ans;
    }
};