2026-07-23：产生至少 K 个峰值的最少操作次数。用go语言，给定一个长度为 n 的整数数组，该数组在逻辑上是首尾相连的（即下标 0 的前一

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。

为了在线性数组上运行动态规划，需要把环形相邻关系正确映射到线性结构上。核心思想是：分别禁止原数组的第一个元素或最后一个元素成为峰值，从而覆盖所有环形下的合法情况（首尾不能同时为峰值，或其中之一不是峰值）。

• •情况 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函数，取两次结果的最小值作为最终答案。

线性数组a（长度为m = n+1）上的 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[i+1]) - a[i] + 1, 0 )：选择位置i作为峰值，需将a[i]提升至严格大于两邻居的最大值，这个操作代价加上前一阶段（left-1个峰值，且最后选的位置在i-2或以前）的代价。

    • • 取min(notChoose, choose)更新到f[i+1]，同时滚动f0、f1以备下一轮使用。

• • 完成k层循环后，f[m-1]即为在该线性数组上选出k个峰值的最小操作次数。

在上述 DP 的choose中，将位置i变为峰值所需的操作次数为max( max(a[i-1], a[i+1]) - a[i] + 1, 0 )。因为只能增加数值，所以必须把a[i]提升到至少max(左邻居, 右邻居) + 1，操作次数即为该值与当前值的差值（若非正则无需操作）。

复杂度分析

• •时间复杂度：solve函数的外层循环执行k次，内层循环长度约为m - 2k量级（m = n+1）。总 DP 转移次数为O(k·(n - k))。最坏情况k ≈ n/2，复杂度达到O(n²)。对于n ≤ 5000，该复杂度在可接受范围内。minOperations调用两次solve，总时间复杂度仍为O(n²)。

• •额外空间复杂度：solve中维护了一维 DP 数组f，长度n+1；每次调用时需要构造临时数组arr1或arr2，大小也为n+1。因此总额外空间复杂度为O(n)。

package main

 import (
    "fmt"
    "math"
)

 // 非环形版本
func solve(a []int, k int) int {
    n := len(a)
    f := make([]int, n)
    for left := 1; left <= k; left++ {
        f0, f1 := f[left*2-2], f[left*2-1]
        f[left*2-1] = math.MaxInt / 2
        for i := left*2 - 1; i < n-1-(k-left)*2; i++ {
            // 选或不选
            notChoose := f[i]
            choose := f0 + max(max(a[i-1], a[i+1])-a[i]+1, 0)
            f0 = f1
            f1 = f[i+1] // 保存旧数据
            f[i+1] = min(notChoose, choose)
        }
    }
    return f[n-1]
}

 func minOperations(nums []int, k int) int {
    n := len(nums)
    if k > n/2 {
        return -1
    }

     cnt := 0
    for i, x := range nums {
        if nums[(i-1+n)%n] < x && x > nums[(i+1)%n] {
            cnt++
        }
    }
    if cnt >= k { // 优化：已经有至少 k 个峰值了，无需操作
        return 0
    }

     // 如果 nums[0] 是峰值，那么 nums[n-1] 不是峰值
    ans1 := solve(append([]int{nums[n-1]}, nums...), k)
    // 如果 nums[0] 不是峰值
    ans2 := solve(append(nums, nums[0]), k)
    return min(ans1, ans2)
}

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

Python完整代码如下：

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

 import math
from typing import List

 def solve(a: List[int], k: int) -> int:
    """非环形版本：在数组 a 中选出 k 个不相邻的峰值所需的最小操作数"""
    n = len(a)
    f = [0] * n
    for left in range(1, k + 1):
        f0, f1 = f[left * 2 - 2], f[left * 2 - 1]
        f[left * 2 - 1] = math.inf
        end = n - 1 - (k - left) * 2
        for i in range(left * 2 - 1, end):
            not_choose = f[i]
            choose = f0 + max(max(a[i - 1], a[i + 1]) - a[i] + 1, 0)
            f0, f1 = f1, f[i + 1]  # 保存旧值并滑动
            f[i + 1] = min(not_choose, choose)
    return f[n - 1]

 def minOperations(nums: List[int], k: int) -> int:
    n = len(nums)
    if k > n // 2:
        return -1

     # 已有峰值计数
    cnt = 0
    for i in range(n):
        if nums[(i - 1) % n] < nums[i] > nums[(i + 1) % n]:
            cnt += 1
    if cnt >= k:
        return 0

     # 情况1：假设原数组的首元素是峰值 -> 尾元素不能是峰值
    arr1 = [nums[-1]] + nums
    ans1 = solve(arr1, k)

     # 情况2：原数组的首元素不是峰值
    arr2 = nums + [nums[0]]
    ans2 = solve(arr2, k)

     return min(ans1, ans2)

 if __name__ == "__main__":
    nums = [2, 1, 2]
    k = 1
    print(minOperations(nums, k))

C++完整代码如下：

#include  

#include  

#include  

#include  


 using namespace std;

 /**
 * 非环形版本：在数组 a 中选出 k 个不相邻的峰值所需的最小操作数
 * @param a 整数数组
 * @param k 需要的峰值个数
 * @return 最小操作数
 */
int solve(const vector& a, int k) {
    int n = a.size();
    vector f(n, 0);
    for (int left = 1; left <= k; ++left) {
        int f0 = f[left * 2 - 2];
        int f1 = f[left * 2 - 1];
        f[left * 2 - 1] = INT_MAX / 2;  // 相当于正无穷
        int end = n - 1 - (k - left) * 2;
        for (int i = left * 2 - 1; i < end; ++i) {
            int notChoose = f[i];
            int choose = f0 + max(max(a[i - 1], a[i + 1]) - a[i] + 1, 0);
            f0 = f1;
            f1 = f[i + 1];   // 保存旧数据
            f[i + 1] = min(notChoose, choose);
        }
    }
    return f[n - 1];
}

 /**
 * 计算使循环数组包含至少 k 个峰值的最小操作数
 * @param nums 循环整数数组
 * @param k 目标峰值个数
 * @return 最小操作数，不可能则返回 -1
 */
int minOperations(const vector& nums, int k) {
    int n = nums.size();
    // 峰值必须不相邻，因此最多 n/2 个
    if (k > n / 2) return -1;

     // 统计已有的峰值个数
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[(i - 1 + n) % n] < nums[i] && nums[i] > nums[(i + 1) % n]) {
            ++cnt;
        }
    }
    if (cnt >= k) return 0;   // 已经满足要求

     // 情况1：假设原数组的首元素是峰值，则尾元素不能是峰值
    vector a1;
    a1.push_back(nums[n - 1]);
    a1.insert(a1.end(), nums.begin(), nums.end());
    int ans1 = solve(a1, k);

     // 情况2：原数组的首元素不是峰值
    vector a2 = nums;
    a2.push_back(nums[0]);
    int ans2 = solve(a2, k);

     return min(ans1, ans2);
}

 int main() {
    vector nums = {2, 1, 2};
    int k = 1;
    cout << minOperations(nums, k) << endl;
    return 0;
}

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