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

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

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

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

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

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

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

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

示例 1:

输出：1

解释：

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

示例 2:

输出：2

解释：

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

示例 3:

输出：0

解释：

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

提示：

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

解题方法：滑动窗口

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

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

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

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

优化

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

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

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

时空复杂度分析

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

AC代码

C++

/* * @LastEditTime: 2026-02-06 19:14:06 */typedeflonglongll;classSolution{private:intgetLastRIndex(vector<int>&nums,ll k){if(nums[0]*k>INT_MAX){returnnums.size()-1;}vector<int>::iterator it=upper_bound(nums.begin(),nums.end(),nums[0]*k);returnmin((long)nums.size()-1,it-nums.begin());}public:intminRemoval(vector<int>&nums,ll k){sort(nums.begin(),nums.end());intkeep=1;for(intl=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;}}returnnums.size()-keep;}};

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

千篇源码题解已开源