Medium

题目描述

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

如果索引 i (0 < i < n - 1) 满足 nums[i] > nums[i - 1] 且 nums[i] > nums[i + 1]，则该索引是特殊的。

你可以执行操作，选择任意索引 i 并将 nums[i] 增加 1。

你的目标是：

  • 最大化特殊索引的数量
  • 最小化达到该最大值所需的总操作数

返回所需的最小总操作数。

示例 1：

输入：nums = [1,2,2]
输出：1
解释：
从 nums = [1, 2, 2] 开始。
将 nums[1] 增加 1，数组变为 [1, 3, 2]。
最终数组 [1, 3, 2] 有 1 个特殊索引，这是可达到的最大值。
无法用更少的操作达到这个特殊索引数量。因此答案是 1。

示例 2：

输入：nums = [2,1,1,3]
输出：2
解释：
从 nums = [2, 1, 1, 3] 开始。
在索引 1 处执行 2 次操作，数组变为 [2, 3, 1, 3]。
最终数组 [2, 3, 1, 3] 有 1 个特殊索引，这是可达到的最大值。因此答案是 2。

示例 3：

输入：nums = [5,2,1,4,3]
输出：4
解释：
从 nums = [5, 2, 1, 4, 3] 开始。
在索引 1 处执行 4 次操作，数组变为 [5, 6, 1, 4, 3]。
最终数组 [5, 6, 1, 4, 3] 有 2 个特殊索引，这是可达到的最大值。因此答案是 4。

约束：

  • 3 <= n <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这是一个动态规划问题。关键观察是相邻的特殊索引会相互影响，因此需要考虑不同的选择策略。

核心思路：

对于每个位置 i，我们有两种选择：

  1. 让 i 成为特殊索引
  2. 不让 i 成为特殊索引

如果选择让 i 成为特殊索引，需要满足：

  • nums[i] > nums[i-1]
  • nums[i] > nums[i+1]

这意味着我们需要将 nums[i] 增加到 max(nums[i-1], nums[i+1]) + 1。

动态规划状态设计：

使用 dp[i][j] 表示处理前 i 个元素，第 i-1 个位置的状态为 j 时的最优结果，其中：

  • j = 0：第 i-1 个位置不是特殊索引
  • j = 1：第 i-1 个位置是特殊索引

每个状态存储一对值 (count, cost)，表示特殊索引数量和最小操作数。

状态转移：

对于位置 i，考虑所有可能的前一个状态，计算当前位置是否可以成为特殊索引以及所需的代价。如果当前位置成为特殊索引，需要确保它比相邻元素都大。

通过动态规划，我们可以找到最大的特殊索引数量，然后在所有达到最大数量的方案中选择操作数最小的。

代码实现

class Solution {
public:
    long long minIncrease(vector<int>& nums) {
        int n = nums.size();
        vector<long long> dp(n, LLONG_MAX);
        dp[0] = 0;
        
        for (int i = 1; i < n - 1; i++) {
            // Case 1: don't make i special
            dp[i] = min(dp[i], dp[i-1]);
            
            // Case 2: make i special
            long long cost = max(0LL, max((long long)nums[i-1] + 1 - nums[i], 
                                        (long long)nums[i+1] + 1 - nums[i]));
            dp[i] = min(dp[i], dp[i-1] + cost);
        }
        
        // Try to maximize special indices using greedy approach
        vector<pair<int, int>> candidates;
        for (int i = 1; i < n - 1; i++) {
            long long cost = max(0LL, max((long long)nums[i-1] + 1 - nums[i],
                                        (long long)nums[i+1] + 1 - nums[i]));
            candidates.push_back({cost, i});
        }
        
        sort(candidates.begin(), candidates.end());
        
        long long result = 0;
        vector<bool> used(n, false);
        
        for (auto& p : candidates) {
            int cost = p.first;
            int idx = p.second;
            
            if (!used[idx-1] && !used[idx] && !used[idx+1]) {
                result += cost;
                used[idx-1] = used[idx] = used[idx+1] = true;
            }
        }
        
        return result;
    }
};

class Solution:
    def minIncrease(self, nums: List[int]) -> int:
        n = len(nums)
        
        # Calculate cost to make each position special
        candidates = []
        for i in range(1, n - 1):
            cost = max(0, max(nums[i-1] + 1 - nums[i], nums[i+1] + 1 - nums[i]))
            candidates.append((cost, i))
        
        # Sort by cost (greedy approach)
        candidates.sort()
        
        result = 0
        used = [False] * n
        
        # Greedily select special indices
        for cost, idx in candidates:
            if not used[idx-1] and not used[idx] and not used[idx+1]:
                result += cost
                used[idx-1] = used[idx] = used[idx+1] = True
        
        return result

public class Solution {
    public long MinIncrease(int[] nums) {
        int n = nums.Length;
        
        var candidates = new List<(long cost, int idx)>();
        for (int i = 1; i < n - 1; i++) {
            long cost = Math.Max(0L, Math.Max((long)nums[i-1] + 1 - nums[i],
                                            (long)nums[i+1] + 1 - nums[i]));
            candidates.Add((cost, i));
        }
        
        candidates.Sort();
        
        long result = 0;
        bool[] used = new bool[n];
        
        foreach (var (cost, idx) in candidates) {
            if (!used[idx-1] && !used[idx] && !used[idx+1]) {
                result += cost;
                used[idx-1] = used[idx] = used[idx+1] = true;
            }
        }
        
        return result;
    }
}

var minIncrease = function(nums) {
    const n = nums.length;
    
    const candidates = [];
    for (let i = 1; i < n - 1; i++) {
        const cost = Math.max(0, Math.max(nums[i-1] + 1 - nums[i], 
                                        nums[i+1] + 1 - nums[i]));
        candidates.push([cost, i]);
    }
    
    candidates.sort((a, b) => a[0] - b[0]);
    
    let result = 0;
    const used = new Array(n).fill(false);
    
    for (const [cost, idx] of candidates) {
        if (!used[idx-1] && !used[idx] && !used[idx+1]) {
            result += cost;
            used[idx-1] = used[idx] = used[idx+1] = true;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：主要由排序操作决定，为 O(n log n)
  • 空间复杂度：需要存储候选位置和使用状态数组，为 O(n)