)
【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 <= 1051 <= nums[i] <= 1091 <= k <= 105
解题方法：滑动窗口
元素顺序不影响结果，首先对原始数组按从小到大排个序。
枚举每一个最小元素的下标，不难发现随着最小元素的增大，最大元素也在增大。
因此可以使用两个指针l ll和r rr分别指向窗口起始下标和结束下标的下一位，那么窗口中元素则是平衡的。
从l = 0 l=0l=0开始不断右移左指针，每次确定右指针的位置，r − l r-lr−l即位当前方案最多保留的元素。
优化
对于初始r rr的确定，一共有三种方法：
- 从后往前遍历
- 二分查找第一个大于n u m s [ 0 ] × k nums[0]\times knums[0]×k的下标 （二分查找小优化）
- 直接不找了，从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和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
