2026-05-31减小数组使其满足条件的最小 K 值。用go语言给定一个正整数数组 nums。对任意正整数 k定义函数 nonPositive(nums, k)把数组中所有元素都至少调整到“非正数”≤0所需的最少操作次数。一次操作允许选择某个下标 i并把 nums[i] 减去 k。你需要找一个整数 kk 为正使得 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整数除法例子x7k3(7-1)/3 2 → 实际需要 3 次7→4→1→-2完全正确。总操作次数 数组每个数的操作次数相加。3. 最终要求找最小的正整数 k满足总操作次数 ≤ k²输入[3,7,5]输出3。二、整体解题思路核心思想这道题用的是二分查找先确定 k 的合理范围下界、上界不用从 1 开始暴力试在这个范围内用二分查找找到最小的满足条件的 k。三、分步骤详细执行过程以 nums [3,7,5] 为例步骤1计算数组长度 nnums [3,7,5]n 3步骤2定义「总操作次数计算函数」给定任意 k快速算出把所有数变 ≤0 需要多少次操作。计算方式总操作次数 n 所有数 (x-1)/k 之和n 是固定偏移量不影响逻辑步骤3计算 k 的「下界」最小可能值为了不浪费时间我们不从头找直接算一个最低起点。下界由两个值取最大数组长度的平方根向上取整数组总和的立方根向上取整代入计算n3 → √3 ≈ 1.732 → 向上取整 2总和37515 → 立方根≈2.466 → 向上取整 3取最大下界 3步骤4计算 k 的「上界」最大可能值用刚才算出的下界 k3代入操作次数函数算出结果操作次数 3 (3-1)/3 (7-1)/3 (5-1)/3 3 0 2 1 6上界 这个操作次数的平方根向上取整√6 ≈ 2.45 → 向上取整 3最终查找范围左3右3步骤5二分查找最小满足条件的 k现在只需要验证 k3 是否满足总操作次数 ≤ k²计算k3k²9总操作次数6 ≤9 ✅ 满足因为查找范围只有 3 这一个数直接确定最小 k 3四、通用完整流程不局限于示例确定计算规则每个数 x 变 ≤0 的最少操作次数(x-1)/k整数除法总操作次数 数组长度 所有数操作次数之和确定二分查找范围下界max(√n 向上取整, 总和立方根向上取整)上界用下界算出的操作次数的平方根向上取整这个范围很小效率极高。二分查找验证在 [下界, 上界] 里找最小 k对每个中间值 k计算总操作次数判断是否 ≤k²满足 → 尝试找更小的 k不满足 → 必须增大 k返回找到的最小 k五、时间复杂度 额外空间复杂度1. 总时间复杂度O(n logM)n数组长度遍历数组计算总和、计算操作次数logM二分查找的次数M是上下界范围非常小几乎可以忽略因为 n 可以到 10⁵这个复杂度完全符合题目要求效率极高。2. 总额外空间复杂度O(1)全程只使用了固定数量的变量n、sum、left、right、ans 等没有开辟任何与数组长度相关的额外空间。总结解题核心二分查找 快速计算操作次数步骤定范围 → 二分验证 → 找最小k时间复杂度O(n)高效处理 10⁵ 数据空间复杂度O(1)常数空间无额外开销Go完整代码如下packagemainimport(fmtmathsort)funcminimumK(nums[]int)int{n:len(nums)nonPositive:func(kint)int{sum:nfor_,x:rangenums{sum(x-1)/k}returnsum}sum:0for_,x:rangenums{sumx}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:leftsort.Search(right-left,func(kint)bool{kleftreturnnonPositive(k)k*k})returnans}funcmain(){nums:[]int{3,7,5}result:minimumK(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathdefminimumK(nums):nlen(nums)defnonPositive(k):totalnforxinnums:total(x-1)//kreturntotal total_sumsum(nums)leftmax(math.ceil(math.sqrt(n)),math.ceil(total_sum**(1/3)))# Python 需要确保 left 是整数leftint(left)rightint(math.ceil(math.sqrt(nonPositive(left))))# 二分查找low,high0,right-leftwhilelowhigh:mid(lowhigh)//2kleftmidifnonPositive(k)k*k:highmidelse:lowmid1ansleftlowreturnansif__name____main__:nums[3,7,5]resultminimumK(nums)print(result)C完整代码如下#includeiostream#includevector#includecmath#includealgorithmusingnamespacestd;intminimumK(vectorintnums){intnnums.size();autononPositive[](intk)-int{intsumn;for(intx:nums){sum(x-1)/k;}returnsum;};intsum0;for(intx:nums){sumx;}intleftmax((int)ceil(sqrt((double)n)),(int)ceil(cbrt((double)sum)));intright(int)ceil(sqrt((double)nonPositive(left)));// 二分查找intansleft;intlow0,highright-left;while(lowhigh){intmid(lowhigh)/2;intkleftmid;if(nonPositive(k)k*k){highmid;}else{lowmid1;}}ansleftlow;returnans;}intmain(){vectorintnums{3,7,5};intresultminimumK(nums);coutresultendl;return0;}