Hard

题目描述

给你一个长度为 n 的环形整数数组 nums。

如果索引 i 的值严格大于其相邻元素，则索引 i 是一个峰值：

  • i 的前一个邻居是 nums[i - 1]（如果 i > 0），否则是 nums[n - 1]。
  • i 的后一个邻居是 nums[i + 1]（如果 i < n - 1），否则是 nums[0]。

你可以执行以下操作任意次数：

  • 选择任意索引 i 并将 nums[i] 增加 1。

返回使数组包含至少 k 个峰值所需的最少操作次数。如果不可能，返回 -1。

示例 1：

输入：nums = [2,1,2], k = 1
输出：1
解释：
为了实现至少 k = 1 个峰值，我们可以将 nums[2] = 2 增加到 3。
此操作后，nums[2] = 3 严格大于其邻居 nums[0] = 2 和 nums[1] = 1。
因此，所需的最少操作次数是 1。

示例 2：

输入：nums = [4,5,3,6], k = 2
输出：0
解释：
数组已经包含至少 k = 2 个峰值，无需任何操作。
索引 1：nums[1] = 5 严格大于其邻居 nums[0] = 4 和 nums[2] = 3。
索引 3：nums[3] = 6 严格大于其邻居 nums[2] = 3 和 nums[0] = 4。
因此，所需的最少操作次数是 0。

示例 3：

输入：nums = [3,7,3], k = 2
输出：-1
解释：
在这个数组中不可能有至少 k = 2 个峰值。因此，答案是 -1。

约束条件：

  • 2 <= n == nums.length <= 5000
  • -10^5 <= nums[i] <= 10^5
  • 0 <= k <= n

解题思路

如果选择下标 i 作为峰值，只需把它增加到严格大于两个原始邻居，代价为：

cost[i] = max(0, max(nums[prev], nums[next]) + 1 - nums[i])

两个相邻下标不可能同时成为峰值；反过来，对任意一组互不相邻的下标，分别支付上述代价后都能成为峰值。因此问题等价于：在一个环上选择恰好 k 个互不相邻的点，使权重和最小。

将环拆成两种互斥情况：

  1. 不选择下标 0，在路径 [1, n - 1] 中选择 k 个点。
  2. 选择下标 0，支付 cost[0]，排除下标 1 和 n - 1，再在路径 [2, n - 2] 中选择 k - 1 个点。

路径 DP 维护“前一个位置未选”和“前一个位置已选”两组状态，并使用滚动数组把空间压缩到 O(k)。环上最多只能选择 floor(n / 2) 个互不相邻点，超过时直接返回 -1。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int n = nums.size();
        if (k == 0) return 0;
        if (k > n / 2) return -1;

        vector<int> cost(n);
        for (int i = 0; i < n; i++) {
            int previous = nums[(i - 1 + n) % n];
            int next = nums[(i + 1) % n];
            cost[i] = max(0, max(previous, next) + 1 - nums[i]);
        }

        const long long INF = 1LL << 60;
        auto solvePath = [&](int left, int right, int need) {
            if (need == 0) return 0LL;
            if (left > right) return INF;

            vector<long long> notSelected(need + 1, INF);
            vector<long long> selected(need + 1, INF);
            notSelected[0] = 0;

            for (int index = left; index <= right; index++) {
                vector<long long> nextNotSelected(need + 1, INF);
                vector<long long> nextSelected(need + 1, INF);
                for (int count = 0; count <= need; count++) {
                    nextNotSelected[count] = min(notSelected[count], selected[count]);
                    if (count > 0 && notSelected[count - 1] != INF) {
                        nextSelected[count] = notSelected[count - 1] + cost[index];
                    }
                }
                notSelected.swap(nextNotSelected);
                selected.swap(nextSelected);
            }

            return min(notSelected[need], selected[need]);
        };

        long long answer = solvePath(1, n - 1, k);
        answer = min(answer, cost[0] + solvePath(2, n - 2, k - 1));
        return answer == INF ? -1 : static_cast<int>(answer);
    }
};

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        n = len(nums)
        if k == 0:
            return 0
        if k > n // 2:
            return -1

        cost = [0] * n
        for i in range(n):
            previous = nums[(i - 1) % n]
            following = nums[(i + 1) % n]
            cost[i] = max(0, max(previous, following) + 1 - nums[i])

        inf = 10**30

        def solve_path(left, right, need):
            if need == 0:
                return 0
            if left > right:
                return inf

            not_selected = [inf] * (need + 1)
            selected = [inf] * (need + 1)
            not_selected[0] = 0

            for index in range(left, right + 1):
                next_not_selected = [inf] * (need + 1)
                next_selected = [inf] * (need + 1)
                for count in range(need + 1):
                    next_not_selected[count] = min(
                        not_selected[count], selected[count]
                    )
                    if count > 0 and not_selected[count - 1] != inf:
                        next_selected[count] = (
                            not_selected[count - 1] + cost[index]
                        )
                not_selected = next_not_selected
                selected = next_selected

            return min(not_selected[need], selected[need])

        answer = solve_path(1, n - 1, k)
        answer = min(answer, cost[0] + solve_path(2, n - 2, k - 1))
        return -1 if answer == inf else answer

public class Solution {
    public int MinOperations(int[] nums, int k) {
        int n = nums.Length;
        if (k == 0) return 0;
        if (k > n / 2) return -1;

        int[] cost = new int[n];
        for (int i = 0; i < n; i++) {
            int previous = nums[(i - 1 + n) % n];
            int following = nums[(i + 1) % n];
            cost[i] = Math.Max(0, Math.Max(previous, following) + 1 - nums[i]);
        }

        const long Inf = long.MaxValue / 4;

        long SolvePath(int left, int right, int need) {
            if (need == 0) return 0;
            if (left > right) return Inf;

            long[] notSelected = new long[need + 1];
            long[] selected = new long[need + 1];
            for (int count = 0; count <= need; count++) {
                notSelected[count] = Inf;
                selected[count] = Inf;
            }
            notSelected[0] = 0;

            for (int index = left; index <= right; index++) {
                long[] nextNotSelected = new long[need + 1];
                long[] nextSelected = new long[need + 1];
                for (int count = 0; count <= need; count++) {
                    nextNotSelected[count] = Math.Min(
                        notSelected[count], selected[count]
                    );
                    nextSelected[count] = Inf;
                    if (count > 0 && notSelected[count - 1] != Inf) {
                        nextSelected[count] = notSelected[count - 1] + cost[index];
                    }
                }
                notSelected = nextNotSelected;
                selected = nextSelected;
            }

            return Math.Min(notSelected[need], selected[need]);
        }

        long answer = SolvePath(1, n - 1, k);
        answer = Math.Min(answer, cost[0] + SolvePath(2, n - 2, k - 1));
        return answer == Inf ? -1 : (int)answer;
    }
}

var minOperations = function(nums, k) {
    const n = nums.length;
    if (k === 0) return 0;
    if (k > Math.floor(n / 2)) return -1;

    const cost = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        const previous = nums[(i - 1 + n) % n];
        const following = nums[(i + 1) % n];
        cost[i] = Math.max(0, Math.max(previous, following) + 1 - nums[i]);
    }

    const solvePath = (left, right, need) => {
        if (need === 0) return 0;
        if (left > right) return Infinity;

        let notSelected = new Array(need + 1).fill(Infinity);
        let selected = new Array(need + 1).fill(Infinity);
        notSelected[0] = 0;

        for (let index = left; index <= right; index++) {
            const nextNotSelected = new Array(need + 1).fill(Infinity);
            const nextSelected = new Array(need + 1).fill(Infinity);
            for (let count = 0; count <= need; count++) {
                nextNotSelected[count] = Math.min(
                    notSelected[count], selected[count]
                );
                if (count > 0 && notSelected[count - 1] !== Infinity) {
                    nextSelected[count] = notSelected[count - 1] + cost[index];
                }
            }
            notSelected = nextNotSelected;
            selected = nextSelected;
        }

        return Math.min(notSelected[need], selected[need]);
    };

    let answer = solvePath(1, n - 1, k);
    answer = Math.min(answer, cost[0] + solvePath(2, n - 2, k - 1));
    return answer === Infinity ? -1 : answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间O(n × k)
空间O(k)