2026-07-23产生至少 K 个峰值的最少操作次数。用go语言给定一个长度为 n 的整数数组该数组在逻辑上是首尾相连的即下标 0 的前一个是 n-1下标 n-1 的后一个是 0。如果一个下标上的元素值比它相邻的两个元素值都大则称该下标为一个“峰值”。这里的相邻关系要考虑循环连接。你可以不断执行以下操作任选一个下标将其对应的值加 1。操作次数没有限制。目标是让数组中峰值的个数至少达到 k。请计算达成该目标所需的最少操作次数。如果无论如何操作都无法得到至少 k 个峰值则返回 -1。2 n nums.length 5000。-100000 nums[i] 100000。0 k n。输入 nums [2,1,2], k 1。输出 1。解释为了实现至少 k 1 个峰值我们可以将 nums[2] 2 增加到 3。执行此操作后nums[2] 3 严格大于其相邻元素 nums[0] 2 和 nums[1] 1。因此所需的最小操作数是 1。题目来自力扣3892。1. 可行性预判与快速返回在一个长度为n的环形数组中两个相邻元素不可能同时为峰值因此峰值数量的理论上限为⌊n/2⌋。若给定的k n/2直接返回-1。遍历整个环形数组统计已经满足“严格大于左右相邻元素”的峰值个数cnt。若cnt ≥ k说明无需任何操作返回0。2. 环形数组的破环处理为了在线性数组上运行动态规划需要把环形相邻关系正确映射到线性结构上。核心思想是分别禁止原数组的第一个元素或最后一个元素成为峰值从而覆盖所有环形下的合法情况首尾不能同时为峰值或其中之一不是峰值。情况 A假定最后一个元素nums[n-1]不是峰值构建新数组arr1 [nums[n-1], nums[0], nums[1], …, nums[n-1]]。这里nums[n-1]被放在最前面为原本缺少左邻居的nums[0]提供正确的环形左邻居而末尾多出的nums[n-1]仅作邻居参考不会被选为峰值。情况 B假定第一个元素nums[0]不是峰值构建新数组arr2 [nums[0], nums[1], …, nums[n-1], nums[0]]。这里nums[0]被放在最后面为原本缺少右邻居的nums[n-1]提供正确的环形右邻居而开头的nums[0]仅作邻居参考不会被选为峰值。对arr1和arr2分别调用线性版本的solve函数取两次结果的最小值作为最终答案。3. 线性版本的动态规划solve 函数线性数组a长度为m n1上的 DP目标是选出恰好 k 个不相邻的位置作为峰值并使总操作代价最小。状态定义f[i]表示在子数组a[0…i]中选出当前阶段所需数量的不相邻峰值的最小操作代价。数组f长度为m初始全0代表选 0 个峰值的代价为 0。逐层递推外层循环left从1到k每次计算在数组中选出left个峰值的最小代价。进入第left层时f中存放的是已选出left-1个峰值的状态。用两个变量f0、f1临时保存前两个位置的旧状态用于滚动更新。将f[left*2-1]设为一个极大值表示在长度不足的区间内无法选出left个不相邻峰值。内层循环i从left*2-1遍历到m-2-(k-left)*2这个上界预留了后续还能选出剩余峰值的空间notChoose f[i]不选择位置i作为新峰值代价沿用已考虑到i的状态。choose f0 max( max(a[i-1], a[i1]) - a[i] 1, 0 )选择位置i作为峰值需将a[i]提升至严格大于两邻居的最大值这个操作代价加上前一阶段left-1个峰值且最后选的位置在i-2或以前的代价。取min(notChoose, choose)更新到f[i1]同时滚动f0、f1以备下一轮使用。完成k层循环后f[m-1]即为在该线性数组上选出k个峰值的最小操作次数。4. 峰值成本的局部计算在上述 DP 的choose中将位置i变为峰值所需的操作次数为max( max(a[i-1], a[i1]) - a[i] 1, 0 )。因为只能增加数值所以必须把a[i]提升到至少max(左邻居, 右邻居) 1操作次数即为该值与当前值的差值若非正则无需操作。复杂度分析时间复杂度solve函数的外层循环执行k次内层循环长度约为m - 2k量级m n1。总 DP 转移次数为O(k·(n - k))。最坏情况k ≈ n/2复杂度达到O(n²)。对于n ≤ 5000该复杂度在可接受范围内。minOperations调用两次solve总时间复杂度仍为O(n²)。额外空间复杂度solve中维护了一维 DP 数组f长度n1每次调用时需要构造临时数组arr1或arr2大小也为n1。因此总额外空间复杂度为O(n)。Go完整代码如下packagemainimport(fmtmath)// 非环形版本funcsolve(a[]int,kint)int{n:len(a)f:make([]int,n)forleft:1;leftk;left{f0,f1:f[left*2-2],f[left*2-1]f[left*2-1]math.MaxInt/2fori:left*2-1;in-1-(k-left)*2;i{// 选或不选notChoose:f[i]choose:f0max(max(a[i-1],a[i1])-a[i]1,0)f0f1 f1f[i1]// 保存旧数据f[i1]min(notChoose,choose)}}returnf[n-1]}funcminOperations(nums[]int,kint)int{n:len(nums)ifkn/2{return-1}cnt:0fori,x:rangenums{ifnums[(i-1n)%n]xxnums[(i1)%n]{cnt}}ifcntk{// 优化已经有至少 k 个峰值了无需操作return0}// 如果 nums[0] 是峰值那么 nums[n-1] 不是峰值ans1:solve(append([]int{nums[n-1]},nums...),k)// 如果 nums[0] 不是峰值ans2:solve(append(nums,nums[0]),k)returnmin(ans1,ans2)}funcmain(){nums:[]int{2,1,2}k:1result:minOperations(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathfromtypingimportListdefsolve(a:List[int],k:int)-int:非环形版本在数组 a 中选出 k 个不相邻的峰值所需的最小操作数nlen(a)f[0]*nforleftinrange(1,k1):f0,f1f[left*2-2],f[left*2-1]f[left*2-1]math.inf endn-1-(k-left)*2foriinrange(left*2-1,end):not_choosef[i]choosef0max(max(a[i-1],a[i1])-a[i]1,0)f0,f1f1,f[i1]# 保存旧值并滑动f[i1]min(not_choose,choose)returnf[n-1]defminOperations(nums:List[int],k:int)-int:nlen(nums)ifkn//2:return-1# 已有峰值计数cnt0foriinrange(n):ifnums[(i-1)%n]nums[i]nums[(i1)%n]:cnt1ifcntk:return0# 情况1假设原数组的首元素是峰值 - 尾元素不能是峰值arr1[nums[-1]]nums ans1solve(arr1,k)# 情况2原数组的首元素不是峰值arr2nums[nums[0]]ans2solve(arr2,k)returnmin(ans1,ans2)if__name____main__:nums[2,1,2]k1print(minOperations(nums,k))C完整代码如下#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;/** * 非环形版本在数组 a 中选出 k 个不相邻的峰值所需的最小操作数 * param a 整数数组 * param k 需要的峰值个数 * return 最小操作数 */intsolve(constvectorinta,intk){intna.size();vectorintf(n,0);for(intleft1;leftk;left){intf0f[left*2-2];intf1f[left*2-1];f[left*2-1]INT_MAX/2;// 相当于正无穷intendn-1-(k-left)*2;for(intileft*2-1;iend;i){intnotChoosef[i];intchoosef0max(max(a[i-1],a[i1])-a[i]1,0);f0f1;f1f[i1];// 保存旧数据f[i1]min(notChoose,choose);}}returnf[n-1];}/** * 计算使循环数组包含至少 k 个峰值的最小操作数 * param nums 循环整数数组 * param k 目标峰值个数 * return 最小操作数不可能则返回 -1 */intminOperations(constvectorintnums,intk){intnnums.size();// 峰值必须不相邻因此最多 n/2 个if(kn/2)return-1;// 统计已有的峰值个数intcnt0;for(inti0;in;i){if(nums[(i-1n)%n]nums[i]nums[i]nums[(i1)%n]){cnt;}}if(cntk)return0;// 已经满足要求// 情况1假设原数组的首元素是峰值则尾元素不能是峰值vectorinta1;a1.push_back(nums[n-1]);a1.insert(a1.end(),nums.begin(),nums.end());intans1solve(a1,k);// 情况2原数组的首元素不是峰值vectorinta2nums;a2.push_back(nums[0]);intans2solve(a2,k);returnmin(ans1,ans2);}intmain(){vectorintnums{2,1,2};intk1;coutminOperations(nums,k)endl;return0;}