遵义公司网站搭建多少钱,wordpress变化,网站建设主管的策划案,wordpress模板在线编辑【LetMeFly】3634.使数组平衡的最少移除数目#xff1a;滑动窗口优化(一次二分查找剪枝) 力扣题目链接#xff1a;https://leetcode.cn/problems/minimum-removals-to-balance-array/ 给你一个整数数组 nums 和一个整数 k。 如果一个数组的 最大 元素的值 至多 是其 最小 …【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 l0l0开始不断右移左指针每次确定右指针的位置r − l r-lr−l即位当前方案最多保留的元素。优化对于初始r rr的确定一共有三种方法从后往前遍历二分查找第一个大于n u m s [ 0 ] × k nums[0]\times knums[0]×k的下标 二分查找小优化直接不找了从r 0 r0r0开始第一次循环时不断往右遍历就会找到如果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(vectorintnums,ll k){if(nums[0]*kINT_MAX){returnnums.size()-1;}vectorint::iterator itupper_bound(nums.begin(),nums.end(),nums[0]*k);returnmin((long)nums.size()-1,it-nums.begin());}public:intminRemoval(vectorintnums,ll k){sort(nums.begin(),nums.end());intkeep1;for(intl0,rgetLastRIndex(nums,k);;l){while(rnums.size()nums[r]nums[l]*k){r;}keepmax(keep,r-l);if(rnums.size()){break;}}returnnums.size()-keep;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源