Medium

题目描述

给你一个整数数组 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

解题思路

这道题的关键洞察是：为了使数组平衡，我们需要找到一个连续的子数组，使得 max <= min * k。

核心思路：

  1. 排序 + 滑动窗口：首先对数组排序，这样在任何连续区间内，最小值就是左端点，最大值就是右端点。

  2. 双指针技巧：使用两个指针 i 和 j 维护一个窗口，其中 nums[i] 是最小值，nums[j] 是最大值。

  3. 窗口扩展策略：对于每个固定的左端点 i，尽可能向右扩展 j，直到 nums[j] > k * nums[i] 为止。这样我们就找到了以 nums[i] 为最小值的最大平衡子数组。

  4. 答案计算：遍历所有可能的左端点，找到最长的平衡子数组，答案就是 n - maxLength。

时间复杂度优化：由于数组已排序，我们可以用双指针技巧，总体时间复杂度为 O(n log n)。

这种方法的优势在于：

  • 排序后问题简化为寻找最长有效区间
  • 双指针确保每个元素最多被访问两次
  • 逻辑清晰，易于理解和实现

代码实现

class Solution {
public:
    int minRemoval(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && nums[j] <= (long long)nums[i] * k) {
                j++;
            }
            maxLen = max(maxLen, j - i);
        }
        
        return n - maxLen;
    }
};

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        max_len = 1
        
        for i in range(n):
            j = i
            while j < n and nums[j] <= nums[i] * k:
                j += 1
            max_len = max(max_len, j - i)
        
        return n - max_len

public class Solution {
    public int MinRemoval(int[] nums, int k) {
        Array.Sort(nums);
        int n = nums.Length;
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && nums[j] <= (long)nums[i] * k) {
                j++;
            }
            maxLen = Math.Max(maxLen, j - i);
        }
        
        return n - maxLen;
    }
}

var minRemoval = function(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let maxLen = 1;
    
    for (let i = 0; i < n; i++) {
        let j = i;
        while (j < n && nums[j] <= nums[i] * k) {
            j++;
        }
        maxLen = Math.max(maxLen, j - i);
    }
    
    return n - maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n + n²)，排序需要 O(n log n)，双重循环最坏情况 O(n²)
空间复杂度O(1)，只使用常数额外空间（排序为原地排序）