2026-07-22：最大化特殊下标数目的最少增加次数。用go语言，给定一个长度为 n 的整数数组，如果某个下标 i（不是第一个也不是最后一个）

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

你可以多次进行操作，每次操作可以任选一个下标，把该位置的数值加 1。

目标有两个：

1. 1. 让特殊位置的数量尽可能多。

2. 2. 在达到这个最大数量的所有方案中，让总的操作次数尽可能少。

要求返回这个最少的总操作次数。

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 是偶数。达到最大数量的方案有多种：可以全选奇数下标、全选偶数下标，或者在某个分界点之前选奇数下标、之后选偶数下标（中间至少空一个位置，保证不相邻）。

对于任意候选位置 i，如果要将它变成峰，需要让它严格大于左右邻居。由于只增加 i 本身，所需最小操作次数为：
need = max(0, max(nums[i-1], nums[i+1]) + 1 - nums[i])
这个代价只取决于原始数组，且各候选峰在不相邻的前提下互不干扰（因为它们不会同时增加邻居）。

3. 奇偶性分流与方案枚举 (1) 计算后缀代价数组suf

从右向左，每隔一个位置累加代价。具体从n-2开始，每次i -= 2，直到i > 0：

• • 若n 为奇数，这个循环会恰好覆盖所有奇数下标（因为 n-2 是奇数）。累加结果suf就是唯一最大峰方案的总代价，直接返回。

• • 若n 为偶数，循环覆盖的是所有偶数下标（n-2 为偶数）。此时suf是“全选偶数下标”方案的总代价，作为初始最优解。

• • 用变量pre表示“当前已选中的前一段奇数下标”的累计代价。

• • 遍历奇数下标 i = 1, 3, 5, … （直到 n-3）：

• • • 将 i 加入奇数段：pre += 代价(i)

  • • 将原本在偶数段中、紧挨着 i 的 i+1 撤销：suf -= 代价(i+1)

  • • 此时方案的结构为：已选奇数下标 [1, i]，中间跳过 i+2，后半段继续选偶数下标 [i+3, n-2]。这种结构保证了峰的数量仍然是最大值，且中间有足够间隔。

  • • 用pre + suf更新全局最小代价。

遍历结束后，ans就是在所有达到最大峰数量的方案中的最小总操作次数。

总时间复杂度

整个过程对数组进行了一次或两次线性扫描（计算 suf 一次，n 为偶数时再扫描一次奇数 i），每次操作仅涉及常数时间的数学运算。因此总时间复杂度为 O(n)。

总额外空间复杂度

算法只使用了常数个变量（suf,pre,ans, 循环变量等），没有开辟与输入规模相关的辅助数组。因此总额外空间复杂度为 O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func minIncrease(nums []int) int64 {
    n := len(nums)
    suf := 0
    for i := n - 2; i > 0; i -= 2 {
        suf += max(max(nums[i-1], nums[i+1])-nums[i]+1, 0)
    }

     if n%2 > 0 {
        // 修改所有奇数下标
        return int64(suf)
    }

     ans := suf // 修改 [2,n-2] 中的所有偶数下标
    pre := 0
    // 枚举修改 [1,i] 中的奇数下标，以及 [i+3,n-2] 中的偶数下标
    for i := 1; i < n-1; i += 2 {
        pre += max(max(nums[i-1], nums[i+1])-nums[i]+1, 0)
        suf -= max(max(nums[i], nums[i+2])-nums[i+1]+1, 0) // 撤销 i+1，撤销后 suf 对应 [i+3,n-2]
        ans = min(ans, pre+suf)
    }

     return int64(ans)
}

 func main() {
    nums := []int{1, 2, 2}
    result := minIncrease(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

 def min_increase(nums: list[int]) -> int:
    n = len(nums)
    # 计算初始 suf：修改从 n-2 开始、步长为 2 的所有位置（偶数下标位置，当 n 为偶数时）
    suf = 0
    for i in range(n - 2, 0, -2):
        suf += max(max(nums[i - 1], nums[i + 1]) - nums[i] + 1, 0)
    # 如果 n 是奇数，直接返回 suf
    if n % 2 == 1:
        return suf
    # n 为偶数时，枚举分割点
    ans = suf  # 初始 ans 为修改所有偶数下标（从 2 到 n-2）
    pre = 0
    # 枚举修改奇数下标 [1, i] 以及偶数下标 [i+3, n-2]
    for i in range(1, n - 1, 2):
        pre += max(max(nums[i - 1], nums[i + 1]) - nums[i] + 1, 0)
        # 撤销 i+1 位置的贡献，suf 变为对应 [i+3, n-2] 的部分
        suf -= max(max(nums[i], nums[i + 2]) - nums[i + 1] + 1, 0)
        ans = min(ans, pre + suf)
    return ans

 # 测试
if __name__ == "__main__":
    nums = [1, 2, 2]
    result = min_increase(nums)
    print(result)

C++完整代码如下：

  

  

  

using namespace std;

 long long minIncrease(vector& nums) {
    int n = nums.size();
    long long suf = 0;

     // 计算初始 suf：修改从 n-2 开始、步长为 2 的所有位置（偶数下标位置）
    for (int i = n - 2; i > 0; i -= 2) {
        suf += max(max(nums[i - 1], nums[i + 1]) - nums[i] + 1, 0);
    }

     // 如果 n 是奇数，直接返回 suf
    if (n % 2 == 1) {
        return suf;
    }

     // n 为偶数时，枚举分割点
    long long ans = suf;  // 初始 ans 为修改所有偶数下标（从 2 到 n-2）
    long long pre = 0;

     // 枚举修改奇数下标 [1, i] 以及偶数下标 [i+3, n-2]
    for (int i = 1; i < n - 1; i += 2) {
        pre += max(max(nums[i - 1], nums[i + 1]) - nums[i] + 1, 0);
        // 撤销 i+1 位置的贡献，suf 变为对应 [i+3, n-2] 的部分
        suf -= max(max(nums[i], nums[i + 2]) - nums[i + 1] + 1, 0);
        ans = min(ans, pre + suf);
    }

     return ans;
}

 int main() {
    vector nums = {1, 2, 2};
    long long result = minIncrease(nums);
    cout << result << endl;
    return 0;
}

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