2026-01-06：使数组平衡的最少移除数目。用go语言，给定一个整数数组 nums 和一个整数 k。我们把满足“数组中最大值与最小值之比不超过 k

福大大架构师每日一题

发布于 2026-01-12 11:09:59

970

2026-01-06：使数组平衡的最少移除数目。用go语言，给定一个整数数组 nums 和一个整数 k。我们把满足“数组中最大值与最小值之比不超过 k”的非空数组称为平衡数组。你被允许从 nums 中去掉任意个元素（但不能把数组清空），要求找到使剩下元素构成平衡数组所需删除的最少元素个数。注意：长度为 1 的数组自动视为平衡。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

1 <= k <= 100000。

输入：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。

题目来自力扣3634。

详细解决步骤

1. 数组排序

首先对输入数组进行升序排序。排序后数组元素从小到大排列，这样便于后续的滑动窗口操作。

对于示例 nums = [1, 6, 2, 9], 排序后变为 [1, 2, 6, 9]。

2. 滑动窗口寻找最长有效子数组

排序后，使用双指针技术维护一个滑动窗口：

• 左指针（left）：表示当前考虑的子数组的起始位置
• 右指针（i）：表示当前考虑的子数组的结束位置

窗口滑动过程如下：

1. 外层循环：右指针i从数组开头遍历到结尾，每次移动一位
2. 内层循环：对于每个右指针位置，检查当前窗口是否满足平衡条件
- • 条件判断：nums[left] * k < nums[i]
- • 如果不满足（即窗口最大值与最小值之比超过k），则左指针向右移动，缩小窗口
3. 更新最大保留长度：对于每个有效的窗口，计算当前窗口长度(i - left + 1)，并与之前记录的最大值比较更新

3. 核心平衡条件理解

平衡数组的条件是：最大值 ≤ 最小值 × k。

在排序后的数组中，对于窗口[left, i]：

• nums[left]是窗口中的最小值（因为数组已排序）
• nums[i]是窗口中的最大值（因为数组已排序）

因此，平衡条件简化为：nums[i] ≤ nums[left] × k。

4. 计算需要删除的元素数量

最终需要删除的最少元素数为：原数组长度 - 最长有效子数组长度。

在示例中，排序后数组为[1, 2, 6, 9]，k=3：

• 最长有效子数组是[2, 6]（长度=2）
• 需要删除的元素数 = 4 - 2 = 2

算法复杂度分析

时间复杂度

• 排序操作：使用Go的slices.Sort()，基于快速排序实现，平均时间复杂度为O(n log n)，其中n是数组长度。
• 滑动窗口遍历：双指针各遍历数组一次，时间复杂度为O(n)。
• 总时间复杂度：由排序步骤主导，为O(n log n)。

空间复杂度

• 排序算法空间复杂度：Go的快速排序实现需要**O(log n)**的栈空间。
• 其他变量：只使用了常数级别的额外空间（几个指针变量）。
• 总空间复杂度：O(log n)（主要由排序算法的递归调用栈引起）。

算法优势

这种解法巧妙地利用了排序后数组的特性，将原本需要检查所有子数组的O(n²)暴力解法优化为O(n log n)的高效算法。滑动窗口技术确保了我们能够在线性时间内找到最优解。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func minRemoval(nums []int, k int)int {
    slices.Sort(nums)
    maxSave, left := 0, 0
    for i, mx := range nums {
        for nums[left]*k < mx {
            left++
        }
        maxSave = max(maxSave, i-left+1)
    }
    returnlen(nums) - maxSave
}

func main() {
    nums := []int{1, 6, 2, 9}
    k := 3
    result := minRemoval(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_removal(nums, k):
    """
    找到最少需要移除的元素数量，使得剩余数组中任意两元素满足 nums[i] * k >= nums[j]
    且 nums[i] <= nums[j]
    
    参数:
        nums: List[int] - 整数数组
        k: int - 比例系数
        
    返回:
        int - 最少需要移除的元素数量
    """
    nums.sort()
    max_save = 0
    left = 0
    
    for i, mx in enumerate(nums):
        # 移动左指针，直到满足条件
        while nums[left] * k < mx:
            left += 1
        # 更新可以保留的最大元素数量
        max_save = max(max_save, i - left + 1)
    
    returnlen(nums) - max_save


def main():
    nums = [1, 6, 2, 9]
    k = 3
    result = min_removal(nums, k)
    print(result)  


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minRemoval(vector<int>& nums, int k) {
    // 首先对数组进行排序
    sort(nums.begin(), nums.end());

    int maxSave = 0;
    int left = 0;

    // 使用滑动窗口找到可以保留的最大元素数
    for (int i = 0; i < nums.size(); i++) {
        // 移动左指针，直到满足条件
        while (left < i && nums[left] * k < nums[i]) {
            left++;
        }
        // 更新可以保留的最大元素数量
        maxSave = max(maxSave, i - left + 1);
    }

    return nums.size() - maxSave;
}

int main() {
    vector<int> nums = {1, 6, 2, 9};
    int k = 3;

    int result = minRemoval(nums, k);
    cout << result << endl;

    return0;
}