这道题的核心是环形打家劫舍 + DP：峰值不能相邻，通过"破环成链"分两种情况处理环形约束，再用滚动数组优化空间避免 MLE。
核心思路
1. 可行性判断：环形数组中峰值不能相邻，理论上限为 ⌊n/2⌋，若 k > n/2 直接返回 -1
2. 破环成链：类似"打家劫舍 II"，分两种情况覆盖所有环形合法方案：
- 情况 A：假设首元素是峰值 → 尾元素不能是峰值，构造 [nums[n-1], nums[0], ..., nums[n-1]]
- 情况 B：假设首元素不是峰值 → 构造 [nums[0], nums[1], ..., nums[n-1], nums[0]]
3. 线性 DP：在构造的数组上，用滚动数组逐层递推选出 k 个不相邻峰值的最小代价
4. 代价计算：让 a[i] 成为峰值需使其严格大于左右邻居，操作次数为 max(0, max(a[i-1], a[i+1]) - a[i] + 1)
Python3 实现
class Solution:
INF = float('inf')
def _solve(self, a, k):
"""
线性版本：在数组 a 中选出 k 个不相邻的峰值所需的最小操作数
使用滚动数组优化空间
"""
n = len(a)
# f[i] 表示在子数组 a[0..i] 中选出当前层所需峰值的最小代价
f = [0] * n
for left in range(1, k + 1):
# f0 = f[left*2-2], f1 = f[left*2-1]（上一层的结果）
f0 = f[left * 2 - 2]
f1 = f[left * 2 - 1]
f[left * 2 - 1] = self.INF # 当前位置初始化为正无穷
# end 剪枝：后面至少要留 (k-left)*2 个位置给剩余峰值
end = n - 1 - (k - left) * 2
for i in range(left * 2 - 1, end):
not_choose = f[i] # 不选 a[i] 作为峰值
# 选 a[i] 作为峰值的代价：需严格大于左右邻居
cost = max(0, max(a[i - 1], a[i + 1]) - a[i] + 1)
choose = f0 + cost
f0 = f1
f1 = f[i + 1] # 保存旧数据供下一轮使用
f[i + 1] = min(not_choose, choose)
return f[n - 1]
def minOperations(self, nums: list[int], k: int) -> int:
n = len(nums)
# 峰值不能相邻，最多 n//2 个
if k > n // 2:
return -1
# 统计已有峰值个数
cnt = 0
for i in range(n):
prev_val = nums[(i - 1 + n) % n]
next_val = nums[(i + 1) % n]
if nums[i] > prev_val and nums[i] > next_val:
cnt += 1
if cnt >= k:
return 0 # 已满足要求
# 情况 A：首元素是峰值 → 尾元素不能是峰值
# 构造 [nums[n-1], nums[0], nums[1], ..., nums[n-1]]
a1 = [nums[n - 1]] + nums[:]
ans1 = self._solve(a1, k)
# 情况 B：首元素不是峰值
# 构造 [nums[0], nums[1], ..., nums[n-1], nums[0]]
a2 = nums[:] + [nums[0]]
ans2 = self._solve(a2, k)
return min(ans1, ans2)
关键点解析
- 破环成链：两种构造方式确保覆盖所有环形合法方案——首尾不能同时为峰值，至少有一个不是峰值
- 滚动数组：f 数组复用，f0/f1 保存上一层旧值，避免 dp[i][j] 二维数组导致 MLE（n=5000 时二维数组开销大）
- 剪枝：end = n - 1 - (k - left) * 2 保证剩余位置足够放下剩余峰值（每个峰值至少隔一个位置）
- 时间复杂度：O(nk)，空间复杂度：O(n)
示例验证
以 nums = [2,1,2], k = 1 为例：
- k=1 ≤ 3//2=1，可行
- 已有峰值：无（2 不大于相邻的 2），cnt=0 < 1
- 情况 A：a1 = [2,2,1,2]，solve 选出 1 个峰值，最小代价 1
- 情况 B：a2 = [2,1,2,2]，solve 选出 1 个峰值，最小代价 1
- 返回 min(1,1) = 1 ✓
这道题最大的坑是卡常和 MLE，二维 DP 容易超时/超内存，滚动数组优化是过题关键。需要我帮你整理一份"环形打家劫舍"类题目的通用模板吗？
