Frontend Interview

Appearance

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

题目链接：https://leetcode.cn/problems/minimum-removals-to-balance-array/

代码 ​

ts
/**
 * 3634. 使数组平衡的最少移除数目
 * https://leetcode.cn/problems/minimum-removals-to-balance-array/
 */

function minRemoval(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let left = 0;
    let res = 0;
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        while (nums[i] > k * nums[left]) {
            left++;
        }
        res = Math.max(res, i - left + 1);
    }
    return len - res;
}

思路 ​

  • 先对数组排序，使得相同或相近的数集中。
  • 用双指针维护一个窗口 [left, i]，要求窗口内的最大值 nums[i] 满足 nums[i] <= k * nums[left]。
  • 对每个 i，不断右移 left 直到满足条件，此时窗口长度 i - left + 1 为当前“可保留”子数组的最大长度。
  • 用 res 记录能保留的最长长度，最终答案为 len - res，即最少移除元素数目。
  • 时间复杂度 O(nlog⁡n)（排序），空间复杂度 O(1)（不计排序开销）。