3634. 使数组平衡的最少移除数目 - 力扣(LeetCode)
条件约束为:
- 剩下的数组中maxNumber≤minNumber*k
思路:
- 排序后就变成了滑动窗口问题,left为minNumber,right为maxNumber。
- 窗口为[left,right],出的条件为(maxNumber+k-1)/k>minNumber。
- 坑点:为什么是/k,不是*k,是避免溢出。用maxNumber+k-1是向上取整。
class Solution {
public int minRemoval(int[] nums, int k) {
int left=0;
Arrays.sort(nums);
int res=0;
for(int i=0;i<nums.length;i++){
while((nums[i]+k-1)/k>nums[left]){
left++;
}
res=Math.max(i-left+1,res);
}
return nums.length-res;
}
}
