🤖 AI总结
主题
环形数组峰值最少操作次数问题
摘要
本文介绍用动态规划解决环形数组产生至少k个峰值的最少操作次数问题，通过破环为线，分别考虑首尾元素是否为峰值两种情况进行DP，时间复杂度O(n²)，空间复杂度O(n)。
关键信息
- 1 使用动态规划求解环形数组中产生至少k个峰值的最小操作次数
- 2 通过破环为线，分别考虑首尾元素是否为峰值两种情况进行DP
- 3 时间复杂度O(n²)，空间复杂度O(n)
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 = 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个峰值的最小操作次数。
4. 峰值成本的局部计算
在上述 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)。
Go完整代码如下：
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助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
