这道题本质是环形打家劫舍 DP峰值不能相邻通过破环成链分两种情况处理环形约束再用滚动数组优化空间避免 MLE。核心思路1. 可行性判断环形数组中峰值不能相邻理论上限为 ⌊n/2⌋若 k n/2 直接返回 -12. 破环成链类似打家劫舍 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[i1]) - a[i] 1)Java 实现class Solution {static final int INF Integer.MAX_VALUE / 2;/*** 线性版本在数组 a 中选出 k 个不相邻的峰值所需的最小操作数* 使用滚动数组优化空间f[i] 表示在子数组 a[0..i] 中选出当前层所需峰值的最小代价*/private int solve(int[] a, int k) {int n a.length;int[] f new int[n]; // 初始全 0表示选 0 个峰值代价为 0for (int left 1; left k; left) {// f0 f[left*2-2], f1 f[left*2-1]上一层的结果int f0 f[left * 2 - 2];int f1 f[left * 2 - 1];f[left * 2 - 1] INF; // 当前位置初始化为正无穷// end 剪枝后面至少要留 (k-left)*2 个位置给剩余峰值int end n - 1 - (k - left) * 2;for (int i left * 2 - 1; i end; i) {int notChoose f[i]; // 不选 a[i] 作为峰值// 选 a[i] 作为峰值的代价需严格大于左右邻居int cost Math.max(0, Math.max(a[i - 1], a[i 1]) - a[i] 1);int choose f0 cost;f0 f1;f1 f[i 1]; // 保存旧数据供下一轮使用f[i 1] Math.min(notChoose, choose);}}return f[n - 1];}public int minOperations(int[] nums, int k) {int n nums.length;// 峰值不能相邻最多 n/2 个if (k n / 2) return -1;// 统计已有峰值个数int cnt 0;for (int i 0; i n; i) {int prev nums[(i - 1 n) % n];int next nums[(i 1) % n];if (nums[i] prev nums[i] next) {cnt;}}if (cnt k) return 0; // 已满足要求// 情况 A首元素是峰值 → 尾元素不能是峰值// 构造 [nums[n-1], nums[0], nums[1], ..., nums[n-1]]int[] a1 new int[n 1];a1[0] nums[n - 1];System.arraycopy(nums, 0, a1, 1, n);int ans1 solve(a1, k);// 情况 B首元素不是峰值// 构造 [nums[0], nums[1], ..., nums[n-1], nums[0]]int[] a2 new int[n 1];System.arraycopy(nums, 0, a2, 0, n);a2[n] nums[0];int ans2 solve(a2, k);return Math.min(ans1, ans2);}}关键点解析- 破环成链两种构造方式确保覆盖所有环形合法方案——首尾不能同时为峰值至少有一个不是峰值- 滚动数组f 数组复用f0/f1 保存上一层旧值避免 dp[i][j] 二维数组导致 MLEn5000 时二维数组开销大- 剪枝end n - 1 - (k - left) * 2 保证剩余位置足够放下剩余峰值每个峰值至少隔一个位置- 时间复杂度O(nk)空间复杂度O(n)示例验证以 nums [2,1,2], k 1 为例- k1 ≤ 3/21可行- 已有峰值无2 不大于相邻的 2cnt0 1- 情况 Aa1 [2,2,1,2]solve 选出 1 个峰值最小代价 1- 情况 Ba2 [2,1,2,2]solve 选出 1 个峰值最小代价 1- 返回 min(1,1) 1 ✓这道题最大的坑是卡常和 MLE二维 DP 容易超时/超内存滚动数组优化是过题关键。 需要我帮你整理一份环形打家劫舍类题目的通用模板吗
