2026-07-22：最大化特殊下标数目的最少增加次数。用go语言，给定一个长度为 n 的整数数组，如果某个下标 i（不是第一个也不是最后一个）满足它对应的元素比左右邻居都大，那么这个位置就算作“特殊

2026-07-22最大化特殊下标数目的最少增加次数。用go语言给定一个长度为 n 的整数数组如果某个下标 i不是第一个也不是最后一个满足它对应的元素比左右邻居都大那么这个位置就算作“特殊位置”。你可以多次进行操作每次操作可以任选一个下标把该位置的数值加 1。目标有两个让特殊位置的数量尽可能多。在达到这个最大数量的所有方案中让总的操作次数尽可能少。要求返回这个最少的总操作次数。3 n 100000。1 nums[i] 1000000000。输入 nums [1,2,2]。输出 1。解释从 nums [1, 2, 2] 开始。将 nums[1] 增加 1数组变为 [1, 3, 2]。最终数组是 [1, 3, 2]有 1 个特殊的下标这是可达到的最大值。不可能用更少的操作达到这个数量的特殊的下标。因此答案是 1。题目来自力扣3891。算法的核心思路如下1. 最大峰数量的结构分析数组首尾不能成为峰因此候选位置为下标 1 到 n-2。两个峰不能相邻因此峰之间至少间隔 1 个位置。最大峰数量只取决于数组长度 n若n 为奇数候选位置个数 n-2 也是奇数。要达到最大数量唯一方案是选择所有奇数下标即 1, 3, 5, …, n-2。若n 为偶数候选位置个数 n-2 是偶数。达到最大数量的方案有多种可以全选奇数下标、全选偶数下标或者在某个分界点之前选奇数下标、之后选偶数下标中间至少空一个位置保证不相邻。2. 单个峰的代价计算对于任意候选位置 i如果要将它变成峰需要让它严格大于左右邻居。由于只增加 i 本身所需最小操作次数为need max(0, max(nums[i-1], nums[i1]) 1 - nums[i])这个代价只取决于原始数组且各候选峰在不相邻的前提下互不干扰因为它们不会同时增加邻居。3. 奇偶性分流与方案枚举(1) 计算后缀代价数组suf从右向左每隔一个位置累加代价。具体从n-2开始每次i - 2直到i 0若n 为奇数这个循环会恰好覆盖所有奇数下标因为 n-2 是奇数。累加结果suf就是唯一最大峰方案的总代价直接返回。若n 为偶数循环覆盖的是所有偶数下标n-2 为偶数。此时suf是“全选偶数下标”方案的总代价作为初始最优解。(2) 偶数长度下的切换枚举仅当 n 为偶数用变量pre表示“当前已选中的前一段奇数下标”的累计代价。遍历奇数下标 i 1, 3, 5, … 直到 n-3将 i 加入奇数段pre 代价(i)将原本在偶数段中、紧挨着 i 的 i1 撤销suf - 代价(i1)此时方案的结构为已选奇数下标 [1, i]中间跳过 i2后半段继续选偶数下标 [i3, n-2]。这种结构保证了峰的数量仍然是最大值且中间有足够间隔。用pre suf更新全局最小代价。遍历结束后ans就是在所有达到最大峰数量的方案中的最小总操作次数。总时间复杂度整个过程对数组进行了一次或两次线性扫描计算 suf 一次n 为偶数时再扫描一次奇数 i每次操作仅涉及常数时间的数学运算。因此总时间复杂度为 O(n)。总额外空间复杂度算法只使用了常数个变量suf,pre,ans, 循环变量等没有开辟与输入规模相关的辅助数组。因此总额外空间复杂度为 O(1)。Go完整代码如下packagemainimport(fmt)funcminIncrease(nums[]int)int64{n:len(nums)suf:0fori:n-2;i0;i-2{sufmax(max(nums[i-1],nums[i1])-nums[i]1,0)}ifn%20{// 修改所有奇数下标returnint64(suf)}ans:suf// 修改 [2,n-2] 中的所有偶数下标pre:0// 枚举修改 [1,i] 中的奇数下标以及 [i3,n-2] 中的偶数下标fori:1;in-1;i2{premax(max(nums[i-1],nums[i1])-nums[i]1,0)suf-max(max(nums[i],nums[i2])-nums[i1]1,0)// 撤销 i1撤销后 suf 对应 [i3,n-2]ansmin(ans,presuf)}returnint64(ans)}funcmain(){nums:[]int{1,2,2}result:minIncrease(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmin_increase(nums:list[int])-int:nlen(nums)# 计算初始 suf修改从 n-2 开始、步长为 2 的所有位置偶数下标位置当 n 为偶数时suf0foriinrange(n-2,0,-2):sufmax(max(nums[i-1],nums[i1])-nums[i]1,0)# 如果 n 是奇数直接返回 sufifn%21:returnsuf# n 为偶数时枚举分割点anssuf# 初始 ans 为修改所有偶数下标从 2 到 n-2pre0# 枚举修改奇数下标 [1, i] 以及偶数下标 [i3, n-2]foriinrange(1,n-1,2):premax(max(nums[i-1],nums[i1])-nums[i]1,0)# 撤销 i1 位置的贡献suf 变为对应 [i3, n-2] 的部分suf-max(max(nums[i],nums[i2])-nums[i1]1,0)ansmin(ans,presuf)returnans# 测试if__name____main__:nums[1,2,2]resultmin_increase(nums)print(result)C完整代码如下#includeiostream#includevector#includealgorithmusingnamespacestd;longlongminIncrease(vectorintnums){intnnums.size();longlongsuf0;// 计算初始 suf修改从 n-2 开始、步长为 2 的所有位置偶数下标位置for(intin-2;i0;i-2){sufmax(max(nums[i-1],nums[i1])-nums[i]1,0);}// 如果 n 是奇数直接返回 sufif(n%21){returnsuf;}// n 为偶数时枚举分割点longlonganssuf;// 初始 ans 为修改所有偶数下标从 2 到 n-2longlongpre0;// 枚举修改奇数下标 [1, i] 以及偶数下标 [i3, n-2]for(inti1;in-1;i2){premax(max(nums[i-1],nums[i1])-nums[i]1,0);// 撤销 i1 位置的贡献suf 变为对应 [i3, n-2] 的部分suf-max(max(nums[i],nums[i2])-nums[i1]1,0);ansmin(ans,presuf);}returnans;}intmain(){vectorintnums{1,2,2};longlongresultminIncrease(nums);coutresultendl;return0;}