题目

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

我们可以将其转化为：

$$\text{结果} = \text{数组总长度} - \text{最多能保留的元素数量}$$

只要我们找到满足条件（平衡）的“最长子序列”，剩下的就是必须删除的最少元素。

在一个无序数组中找子序列，通常比较困难。但对于这道题，元素在原数组中的相对位置并不影响 min 和 max 的值。

核心结论： 我们可以先对数组进行排序。

排序后，假设我们选择保留的子序列下标范围是 $[i, j]$（$i \le j$）：

该子序列的最小值必然是 $nums[i]$（左端点）。
该子序列的最大值必然是 $nums[j]$（右端点）。
为了让保留的元素数量最多，如果 $nums[i]$ 和 $nums[j]$ 满足条件（即 $nums[j] \le nums[i] \times k$），那么 $i$ 到 $j$ 之间的所有元素一定也都满足条件（因为它们都在 min 和 max 之间）。

因此，问题进一步转化为：

在排序后的数组中，寻找一个最长的连续子数组，满足：

$$nums[right] \le nums[left] \times k$$

由于数组已排序，$nums[right]$ 随着 right 的增加单调递增。这是一个典型的可以用 滑动窗口（双指针） 解决的问题。

具体步骤：

排序：将 nums 从小到大排序。
初始化：设置两个指针 left = 0, right = 0，以及一个变量 max_len = 0 来记录满足条件的最长窗口长度。
遍历：
- 让 right 指针从 0 遍历到 $n-1$。
- 对于每一个 right，检查当前窗口是否“平衡”，即：$nums[right] > nums[left] \times k$。
- 如果条件不满足（即最大值超过了最小值的 $k$ 倍），说明当前的最小值 $nums[left]$ 太小了，“拖累”了窗口的扩展。此时需要收缩左边界，即 left++，直到条件再次满足。
- 更新结果：每次循环计算当前窗口长度 $right - left + 1$，并更新 max_len。
返回：$nums.length - max_len$。

时间复杂度：$O(N \log N)$
- 排序需要 $O(N \log N)$。
- 滑动窗口遍历只需要 $O(N)$（left 和 right 指针各走一遍数组）。
- 整体由排序主导。
空间复杂度：$O(1)$ 或 $O(\log N)$
- 取决于排序算法的实现空间，如果不考虑排序的栈空间，则是 $O(1)$。

具体代码

func minRemoval(nums []int, k int) int {
	// 1. 排序：这是使用滑动窗口的前提，将子序列问题转化为子数组问题
	sort.Ints(nums)

	left := 0
	maxKeep := 0

	// 2. 滑动窗口遍历
	for right, x := range nums {
		// 检查当前窗口是否平衡：nums[right] <= nums[left] * k
		// 使用 int64 避免 nums[left] * k 在极端数据下可能发生的溢出
		for int64(x) > int64(nums[left])*int64(k) {
			left++
		}

		// 更新满足条件的最大窗口长度
		// 当前窗口长度为 right - left + 1
		if currentLen := right - left + 1; currentLen > maxKeep {
			maxKeep = currentLen
		}
	}

	// 3. 结果转化：总数 - 最多能保留的数
	return len(nums) - maxKeep
}

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

beautifulremi

题目

解题思路

具体代码