3634.使数组平衡的最少移除数目：滑动窗口+优化(一次二分查找+剪枝)

【LetMeFly】3634.使数组平衡的最少移除数目：滑动窗口+优化(一次二分查找+剪枝)

力扣题目链接：https://leetcode.cn/problems/minimum-removals-to-balance-array/

给你一个整数数组 nums 和一个整数 k。

如果一个数组的 最大 元素的值 至多 是其 最小 元素的 k 倍，则该数组被称为是 平衡 的。

你可以从 nums 中移除 任意 数量的元素，但不能使其变为 空 数组。

返回为了使剩余数组平衡，需要移除的元素的 最小 数量。

注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。

 

示例 1:

输入：nums = [2,1,5], k = 2

输出：1

解释：

• 移除 nums[2] = 5 得到 nums = [2, 1]。
• 现在 max = 2, min = 1，且 max <= min * k，因为 2 <= 1 * 2。因此，答案是 1。

示例 2:

输入：nums = [1,6,2,9], k = 3

输出：2

解释：

• 移除 nums[0] = 1 和 nums[3] = 9 得到 nums = [6, 2]。
• 现在 max = 6, min = 2，且 max <= min * k，因为 6 <= 2 * 3。因此，答案是 2。

示例 3:

输入：nums = [4,6], k = 2

输出：0

解释：

• 由于 nums 已经平衡，因为 6 <= 4 * 2，所以不需要移除任何元素。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 105

解题方法：滑动窗口

元素顺序不影响结果，首先对原始数组按从小到大排个序。

枚举每一个最小元素的下标，不难发现随着最小元素的增大，最大元素也在增大。

因此可以使用两个指针$l$和$r$分别指向窗口起始下标和结束下标的下一位，那么窗口中元素则是平衡的。

从$l=0$开始不断右移左指针，每次确定右指针的位置，$r-l$即位当前方案最多保留的元素。

优化

对于初始$r$的确定，一共有三种方法：

1. 从后往前遍历
2. 二分查找第一个大于$nums[0]\times k$的下标 （二分查找小优化）
3. 直接不找了，从$r=0$开始，第一次循环时不断往右遍历就会找到

如果$r$指针已经移出数组边界，则可提前结束左指针的右移。

时空复杂度分析

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-02-06 19:14:06
 */
typedef long long ll;
class Solution {
private:
    int getLastRIndex(vector<int>& nums, ll k) {
        if (nums[0] * k > INT_MAX) {
            return nums.size() - 1;
        }
        vector<int>::iterator it = upper_bound(nums.begin(), nums.end(), nums[0] * k);
        return min((long)nums.size() - 1, it - nums.begin());
    }
public:
    int minRemoval(vector<int>& nums, ll k) {
        sort(nums.begin(), nums.end());
        int keep = 1;

        for (int l = 0, r = getLastRIndex(nums, k); ; l++) {
            while (r < nums.size() && nums[r] <= nums[l] * k) {
                r++;
            }
            keep = max(keep, r - l);
            if (r == nums.size()) {
                break;
            }
        }
        return nums.size() - keep;
    }
};

不可for (int l = 0, r = getLastRIndex(nums, k); r < nums.size(); l++) {，否则可能一轮循环都进不去。

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源