2026-05-31：减小数组使其满足条件的最小 K 值。用go语言，给定一个正整数数组 nums。对任意正整数 k，定义函数 nonPositive(...

2026-05-31：减小数组使其满足条件的最小 K 值。用go语言，给定一个正整数数组 nums。对任意正整数 k，定义函数 nonPositive(nums, k)：把数组中所有元素都至少调整到“非正数”（≤0）所需的最少操作次数。一次操作允许选择某个下标 i，并把 nums[i] 减去 k。

你需要找一个整数 k（k 为正）使得 nonPositive(nums, k) <= k²，并返回满足条件的最小 k。

1 <= nums.length <= 10⁵。

1 <= nums[i] <= 10⁵。

输入： nums = [3,7,5]。

输出： 3。

解释：

当 k = 3 时，nonPositive(nums, k) = 6 <= k²。

减少 nums[0] = 3 一次。nums[0] 变为 3 - 3 = 0。

减少 nums[1] = 7 三次。nums[1] 变为 7 - 3 - 3 - 3 = -2。

减少 nums[2] = 5 两次。nums[2] 变为 5 - 3 - 3 = -1。

题目来自力扣3824。

详细过程拆解 一、先彻底搞懂题目核心定义 1. 什么是「一次操作」？

选数组里任意一个数，减去 k。
可以对同一个数减多次。

2. 什么是nonPositive(nums, k)

把数组所有数都变成 ≤0所需的最少总操作次数。

计算规则（核心公式）：
对一个数x，要变成 ≤0，最少需要减多少次 k？
次数 = 向上取整(x / k) → 简化写法：(x - 1) / k（整数除法）

例子：x=7，k=3
(7-1)/3 = 2 → 实际需要 3 次（7→4→1→-2），完全正确。

总操作次数 = 数组每个数的操作次数相加。

3. 最终要求

找最小的正整数 k，满足：
总操作次数 ≤ k²

输入[3,7,5]，输出3。

二、整体解题思路（核心思想）

这道题用的是二分查找：

1. 1. 先确定 k 的合理范围（下界、上界），不用从 1 开始暴力试；

2. 2. 在这个范围内用二分查找，找到最小的满足条件的 k。

nums = [3,7,5]
n = 3

步骤2：定义「总操作次数计算函数」

给定任意 k，快速算出：把所有数变 ≤0 需要多少次操作。

计算方式：
总操作次数 = n + 所有数 (x-1)/k 之和
（n 是固定偏移量，不影响逻辑）

步骤3：计算 k 的「下界」（最小可能值）

为了不浪费时间，我们不从头找，直接算一个最低起点。
下界由两个值取最大：

1. 1. 数组长度的平方根（向上取整）

2. 2. 数组总和的立方根（向上取整）

代入计算：
n=3 → √3 ≈ 1.732 → 向上取整 =2
总和=3+7+5=15 → 立方根≈2.466 → 向上取整 =3

取最大：下界 = 3

步骤4：计算 k 的「上界」（最大可能值）

用刚才算出的下界 k=3，代入操作次数函数，算出结果：
操作次数 = 3 + (3-1)/3 + (7-1)/3 + (5-1)/3
= 3 + 0 + 2 + 1 =6

上界 = 这个操作次数的平方根（向上取整）
√6 ≈ 2.45 → 向上取整 =3

最终：
查找范围：左=3，右=3

步骤5：二分查找最小满足条件的 k

现在只需要验证 k=3 是否满足：
总操作次数 ≤ k²

计算：
k=3，k²=9
总操作次数=6 ≤9 ✅ 满足

因为查找范围只有 3 这一个数，直接确定：
最小 k = 3

四、通用完整流程（不局限于示例）

1. 1.确定计算规则
   每个数 x 变 ≤0 的最少操作次数：(x-1)/k（整数除法）
   总操作次数 = 数组长度 + 所有数操作次数之和

2. 2.确定二分查找范围

• • 下界：max(√n 向上取整, 总和立方根向上取整)

• • 上界：用下界算出的操作次数的平方根向上取整
  这个范围很小，效率极高。

3.二分查找验证
在 [下界, 上界] 里找最小 k：
对每个中间值 k，计算总操作次数，判断是否 ≤k²：

• • 满足 → 尝试找更小的 k

• • 不满足 → 必须增大 k

4.返回找到的最小 k

五、时间复杂度 & 额外空间复杂度 1. 总时间复杂度

O(n + logM)

• • n：数组长度，遍历数组计算总和、计算操作次数

• • logM：二分查找的次数（M是上下界范围，非常小，几乎可以忽略）

因为 n 可以到 10⁵，这个复杂度完全符合题目要求，效率极高。

2. 总额外空间复杂度

O(1)
全程只使用了固定数量的变量（n、sum、left、right、ans 等），没有开辟任何与数组长度相关的额外空间。

总结

1. 1. 解题核心：二分查找 + 快速计算操作次数

2. 2. 步骤：定范围 → 二分验证 → 找最小k

3. 3. 时间复杂度：O(n)（高效处理 10⁵ 数据）

4. 4. 空间复杂度：O(1)（常数空间，无额外开销）

package main

 import (
    "fmt"
    "math"
    "sort"
)

 func minimumK(nums []int)int {
    n := len(nums)
    nonPositive := func(k int)int {
        sum := n
        for _, x := range nums {
            sum += (x - 1) / k
        }
        return sum
    }

     sum := 0
    for _, x := range nums {
        sum += x
    }

     left := max(int(math.Ceil(math.Sqrt(float64(n)))), int(math.Ceil(math.Cbrt(float64(sum))))) // 答案的下界
    right := int(math.Ceil(math.Sqrt(float64(nonPositive(left)))))                              // 答案的上界
    ans := left + sort.Search(right-left, func(k int)bool {
        k += left
        return nonPositive(k) <= k*k
    })
    return ans
}

 func main() {
    nums := []int{3, 7, 5}
    result := minimumK(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

 import math

 def minimumK(nums):
    n = len(nums)
    def nonPositive(k):
        total = n
        for x in nums:
            total += (x - 1) // k
        return total
    total_sum = sum(nums)
    left = max(
        math.ceil(math.sqrt(n)),
        math.ceil(total_sum ** (1/3))
    )
    # Python 需要确保 left 是整数
    left = int(left)
    right = int(math.ceil(math.sqrt(nonPositive(left))))
    # 二分查找
    low, high = 0, right - left
    while low < high:
        mid = (low + high) // 2
        k = left + mid
        if nonPositive(k) <= k * k:
            high = mid
        else:
            low = mid + 1
    ans = left + low
    return ans

 if __name__ == "__main__":
    nums = [3, 7, 5]
    result = minimumK(nums)
    print(result)

C++完整代码如下：

  

  

  

  


 using namespace std;

 int minimumK(vector& nums) {
    int n = nums.size();

     auto nonPositive = [&](int k) -> int {
        int sum = n;
        for (int x : nums) {
            sum += (x - 1) / k;
        }
        return sum;
    };

     int sum = 0;
    for (int x : nums) {
        sum += x;
    }

     int left = max(
        (int)ceil(sqrt((double)n)),
        (int)ceil(cbrt((double)sum))
        );

     int right = (int)ceil(sqrt((double)nonPositive(left)));

     // 二分查找
    int ans = left;
    int low = 0, high = right - left;
    while (low < high) {
        int mid = (low + high) / 2;
        int k = left + mid;
        if (nonPositive(k) <= k * k) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

     ans = left + low;
    return ans;
}

 int main() {
    vector nums = {3, 7, 5};
    int result = minimumK(nums);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。