3634. 使數組平衡的最少移除數目

思路

根據題目描述，可以移除任意數量的元素，不要求連續，就相當於在陣列當中選一些數字保留，
保留的數字中，範圍要在最小數字 $\times{k}$ 以下。

既然順序不要求，就可以排序陣列，此時就有了單調性：
如果選擇位置 $i$ 作為最小值，最右邊的範圍可以到 $j$，
那麼選擇位置 $i+1$ 作為最小值，最右邊的範圍會 $\geq{j}$，
因此可以用滑動窗口去解決這個問題。

程式碼

排序 + 滑動窗口

class Solution {
public:
    int minRemoval(vector<int>& nums, int k) {
        ranges::sort(nums);
        // 貪心：如果最極端的兩個數值都是平衡的，就不需要刪除任何數字。
        if(nums.back() <= 1LL * nums[0] * k) return 0;
        int n = nums.size();
        int res = 0; // 紀錄保留數字的最長長度
        for(int i = 0, j = 0; i < n; i++) {
            // 當不平衡的時候，改變左邊邊界，讓加入的數字可以符合條件
            // 不需要判斷 j 是否越界，因為當 i == j 的時候，一定會跳出迴圈
            while(nums[i] > 1LL * nums[j] * k) { 
                ++j;
            }
            res = max(res, i - j + 1); // 閉區間
        }   
        return n - res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$