leetcode 3634

3634: 使数组平衡的最少移除数目

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

由于我们只关心剩余元素的最小值和最大值，不关心元素的顺序，所以可以先从小到大排序，方便后续计算。

枚举最大值 nums[i]，那么最小值 nums[left] 必须满足 nums[left]*k >=nums[i]。由于排序了，所以这些元素在数组中是连续的，问题转化成一个标准的滑动窗口模型。如果不满足上式，则把 left 加一，直到满足上式。

内层循环结束后，用窗口长度 i−left+1 更新保留元素个数的最大值maxSave。最终答案为 n−maxSave。

class Solution { public: int minRemoval(vector<int>& nums, int k) { ranges::sort(nums); int max_save=0,left=0,n=nums.size(); //枚举最大值 for(int i=0;i<n;i++){ while((long long)nums[left]*k<nums[i]) left++; //滑动窗口 max_save=max(max_save,i-left+1); } return n-max_save; } };

tips:下面这种写法会超出时间限制。

class Solution { public: int minRemoval(vector<int>& nums, int k) { ranges::sort(nums); int max_save=0,n=nums.size(); //枚举最大值 for(int i=n-1;i>=0;i--){ int left=0; while((long long)nums[left]*k<nums[i]) left++; max_save=max(max_save,i-left+1); } return n-max_save; } };