M3634.使数组平衡的最少移除数目

sliding window, 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 <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^5

这个问题可以通过排序 + 滑动窗口（双指针）的方法来解决。

核心思路

目标： 使得剩余数组中最大值 $\leq$ 最小值 $\times k$ 。为了移除最少的元素，我们需要保留尽可能多的元素。
排序： 首先将数组按升序排列。排序后，如果我们选择 nums[i] 作为平衡数组中的最小值，那么该数组中能包含的最大值不能超过 nums[i] * k。
滑动窗口：
- 维护一个窗口 $[l e f t, r i g h t]$ ，其中 nums[left] 是窗口内的最小值。
- 对于每一个确定的左端点 left，向右移动右端点 right，直到 nums[right] 超过了 nums[left] * k 的范围。
- 在这个窗口 [left, right-1] 里的所有元素都满足平衡条件。窗口的长度即为 right - left。
- 遍历所有的 left，记录窗口长度的最大值。
计算结果： 最小移除数目 = 总长度 - 最大保留长度。

复杂度分析

时间复杂度： $O (N \log N)$ ，主要耗时在对数组进行排序。之后的滑动窗口遍历数组只需 $O (N)$ 。
空间复杂度： $O (\log N)$ 或 $O (N)$ ，取决于排序算法的实现空间开销。

Python 代码实现

python

from typing import List

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        # 1. 排序，以便使用滑动窗口
        nums.sort()
        n = len(nums)
        
        max_keep = 0
        right = 0
        
        # 2. 遍历每一个元素作为最小值的情况
        for left in range(n):
            # 计算当前最小值能允许的最大值
            target = nums[left] * k
            
            # 3. 移动右指针，寻找在这个最小值限制下最多能包含到哪个元素
            # 因为数组已排序，right 不需要重置，可以继续向右移动
            while right < n and nums[right] <= target:
                right += 1
            
            # 当前窗口 [left, right-1] 内的元素都是满足条件的
            # 窗口长度为 right - left
            max_keep = max(max_keep, right - left)
            
            # 优化：如果剩余的元素已经不可能超过当前的 max_keep，可以提前结束
            if n - left <= max_keep:
                break
                
        # 4. 最小移除数 = 总数 - 最大保留数
        return n - max_keep

M3634.使数组平衡的最少移除数目 ​

M3634.使数组平衡的最少移除数目