What does 'balanced' mean in Minimum Removals to Balance Array?

Balanced means the maximum element in the remaining array is at most k times the minimum element.

Can the array be empty after removals?

No, at least one element must remain in the array after removals.

Is sorting necessary to solve this problem efficiently?

Yes, sorting allows the two-pointer window approach to check the k-times condition in linear time after sorting.

What is the core pattern for this problem?

The core pattern is minimum removals to achieve a subarray satisfying a max-to-min ratio using a sliding window.

What is the expected time complexity?

Time complexity is O(n log n) due to sorting, followed by O(n) for the two-pointer scan.

#3634

Medium

auto_awesomeminimum·removals·to·balance·数组·core·interview·pattern

LeetCode 题解工作台

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

给你一个整数数组 nums 和一个整数 k 。如果一个数组的最大元素的值至多是其最小元素的 k 倍，则该数组被称为是平衡的。你可以从 nums 中移除任意数量的元素，但不能使其变为空数组。返回为了使剩余数组平衡，需要移除的元素的最小数量。注意：大小为 1 的数组…

题目描述

给你一个整数数组 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⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁵

lightbulb

解题思路

方法一：排序 + 二分查找

我们首先对数组进行排序，然后我们从小到大枚举每个元素 $\textit{nums}[i]$ 作为平衡数组的最小值，那么平衡数组的最大值 $\textit{max}$ 必须满足 $\textit{max} \leq \textit{nums}[i] \times k$ 。因此，我们可以使用二分查找来找到第一个大于 $\textit{nums}[i] \times k$ 的元素的下标 $j$ ，那么此时平衡数组的长度为 $j - i$ ，我们记录下最大的长度 $\textit{cnt}$ ，最后的答案就是数组长度减去 $\textit{cnt}$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        nums.sort()
        cnt = 0
        for i, x in enumerate(nums):
            j = bisect_right(nums, k * x)
            cnt = max(cnt, j - i)
        return len(nums) - cnt

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting is likely expected to simplify the ratio check.
question_mark
Sliding window hints at using two pointers to maximize the valid subarray length.
question_mark
They may probe edge cases like duplicates or large k values to check correctness.

warning

常见陷阱

外企场景

error
Forgetting that removing elements cannot leave the array empty.
error
Incorrectly checking the k-times condition without sorting first.
error
Using nested loops leading to O(n^2) instead of two-pointer linear scan after sorting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimum removals when the array must remain contiguous after removal.
arrow_right_alt
Balance the array using only even-indexed elements with the k-times condition.
arrow_right_alt
Compute the minimum removals when elements can be doubled or halved instead of removed.

help

常见问题

外企场景

探索更多题目 →

auto_awesome

继续模式

minimum·removals·to·balance·数组·core·interview·pattern

用同一解题框架扩展到更多题目。

arrow_forward signal_cellular_alt

同难度题单

中等

按当前难度继续强化稳定输出。

arrow_forward