使数组平衡的最少移除数目-LeetCode

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

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums 和一个整数 k。
你需要移除最少数量的元素，使得剩余数组中最大值不超过最小值的 k 倍。
即：对于剩余数组中的任意元素，满足 max <= min * k。
请你返回最少需要移除的元素个数。

说明：

• 如果数组为空或只有一个元素，天然满足条件。
• 题目等价于寻找一个最长的子序列，使得该子序列满足上述倍数关系。

示例：

• 示例 1：

  输入: nums = [1, 3, 6, 8], k = 2
  输出: 2
  解释: 
  排序后为 [1, 3, 6, 8]。
  我们可以保留 [3, 6] (6 <= 3*2) 或者 [6, 8] (8 <= 6*2)，最长长度为 2。
  需要移除的元素数量 = 4 - 2 = 2。

• 示例 2：

  输入: nums = [1, 1, 1], k = 1
  输出: 0
  解释: 所有元素相等，不需要移除。

💻 解题思路

思路1：排序 + 滑动窗口

1. 排序：
   • 由于只关心数值的倍数关系，顺序无关紧要。
   • 排序后，子序列的最大值和最小值分别对应区间的右端点和左端点。
2. 维护窗口：
   • 维护一个窗口 [left, right]，保证窗口内的最大值不超过最小值的 k 倍。
   • 即：nums[right] <= nums[left] * k。
3. 滑动逻辑：
   • 遍历 right 指针扩展窗口。
   • 如果 nums[left] * k < nums[right]，说明当前窗口不满足条件，移动 left 指针直到满足条件。
4. 计算结果：
   • 记录满足条件的窗口最大长度 ans。
   • 最少移除数量 = 总长度 n - 最长合法窗口长度 ans。

思路1：代码实现

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if n == 1:
            return 0
        ans = 0
        left = 0
        nums.sort()
        for right, num in enumerate(nums):
            while nums[left] * k < num:
                left += 1
            ans = max(ans, right - left + 1)
        return n - ans

思路1：📊 性能分析

复杂度验证

• 时间复杂度：$O(n \log n)$
  • 排序消耗 $O(n \log n)$，双指针遍历消耗 $O(n)$。
• 空间复杂度：$O(1)$
  • 只使用了常数级额外空间（不考虑排序的系统栈空间）。

思考

1. 为什么 nums[left] * k < num 时要移动 left？
   • 因为 num 是当前窗口的最大值，nums[left] 是当前窗口的最小值。
   • 如果 最小值 * k < 最大值，说明倍数关系不成立，必须丢弃最小值（移动 left），尝试寻找更大的最小值。
2. 为什么排序是关键？
   • 排序将“任意子序列”问题转化为“连续子数组”问题，使得滑动窗口算法成立。