3634. Minimum Removals to Balance Array

📘 題目敘述

給你一個整數陣列 nums 和一個整數 k。

如果一個陣列的最大元素值 至多 是最小元素的 k 倍（也就是 max <= min * k），則這個陣列被稱為 balanced。

你可以從 nums 中移除任意數量的元素（但不能把陣列變成空的）。請回傳要使剩下的陣列變成 balanced 所需移除的最少元素數量。

補充：長度為 1 的陣列一定是 balanced。

條件限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^5

🧠 解題思路

把問題換個角度：

與其問「最少要刪幾個」，不如問「最多能留下幾個」。

如果最多能留下 best 個元素，使它們滿足 max <= min * k，那最少移除數量就是 n - best。

怎麼找最多能留下幾個？

1. 先把 nums 排序。若固定 nums[l] 當目前最小值，能留下的元素都必須滿足 nums[x] <= nums[l] * k。
2. 排序後對每個固定 l，合法右邊界會形成連續區間，所以可用雙指標。
3. l 從左到右枚舉；r 只往右擴，直到不再滿足條件。
4. 每次用 best = max(best, r - l) 更新最大可保留長度。

所有變數

• nums：輸入陣列（會先排序）
• k：倍數限制（要滿足 max <= min * k）
• l：左指標（目前區間最小值位置）
• r：右指標（指向第一個不合法位置，區間為 [l, r)）
• best：目前找到最多能保留的元素數量

🪜 主要流程步驟

1. 先排序，讓合法區間連續

• sort(nums.begin(), nums.end())

2. 用雙指標找每個 l 的最遠 r

• 若 r < l，先把 r 拉回 l。
• 持續擴張 r，只要滿足 nums[r] <= nums[l] * k。
• 擴不動時，[l, r) 就是以 nums[l] 為最小值時可保留的最大區間。
• 更新 best = max(best, r - l)。

3. 從最多保留換回最少移除

• 答案為 n - best。

💻 程式碼實作

class Solution {
public:
    int minRemoval(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int r = 0;
        int best = 1;

        for (int l = 0; l < n; l++) {
            if (r < l) {
                r = l;
            }
            while (r < n && (long long)nums[r] <= (long long)nums[l] * k) {
                r++;
            }
            best = max(best, r - l);
        }

        return n - best;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-removals-to-balance-array/