nums[i] = max(nums[i], nums[i-1] + 1)

线性动态规划：最少操作使数组递增 题目描述 给定一个整数数组 nums ，每次操作可以选择一个元素将其增加 1。请问最少需要多少次操作，才能使数组变成严格递增的（即对于每个 i ，有 nums[i] < nums[i+1] ）？ 示例 输入： nums = [1,1,1] 输出： 3 解释：通过 3 次操作可将数组变为 [1,2,3] 。 输入： nums = [1,5,2,4,1] 输出： 14 解释：通过 14 次操作可将数组变为 [1,5,6,7,8] 。 解题过程 步骤 1：理解问题与目标 数组必须严格递增，即每个元素必须大于前一个元素。 只能通过增加元素的值来调整，不能减少。 目标是使操作次数最少。 关键思路 ： 对于每个位置 i （ i ≥ 1 ），必须满足 nums[i] > nums[i-1] 。如果 nums[i] 已经大于 nums[i-1] ，则无需操作；否则，需要将 nums[i] 增加到至少 nums[i-1] + 1 。 步骤 2：设计动态规划状态 定义 dp[i] 表示处理到第 i 个元素时，使前 i 个元素严格递增所需的最小操作次数。 但这里有一个问题： dp[i] 依赖于前一个元素的值，而前一个元素的值可能被操作过，因此需要记录当前元素的值。 调整状态定义 ： 定义 dp[i][v] 表示将前 i 个元素变为严格递增，且第 i 个元素的值调整为 v 所需的最小操作次数。 但 v 的范围可能很大（例如 1e9 ），直接枚举不可行。 步骤 3：优化状态表示 观察发现，最优解中每个元素的值要么是原始值，要么是前一个元素的值加 1（因为增加过多只会浪费操作次数）。 因此，第 i 个元素的可能取值是： 原始值 nums[i] 前一个元素调整后的值加 1 但前一个元素调整后的值又依赖于更前面的元素，这会导致状态数爆炸。 步骤 4：贪心思路 实际上，这个问题可以用贪心法解决： 从第二个元素开始遍历，如果当前元素 nums[i] 小于等于前一个元素 nums[i-1] ，则将其增加到 nums[i-1] + 1 ，操作次数增加 (nums[i-1] + 1 - nums[i]) 。 但这样正确吗？ 反例 ： nums = [1, 1, 1] 按贪心： i=1: nums[ 1]=1 ≤ nums[ 0 ]=1 → 增加到 2，操作次数=1 i=2: nums[ 2]=1 ≤ nums[ 1 ]=2 → 增加到 3，操作次数=1+2=3 结果正确。 再试 nums = [1, 5, 2, 4, 1] ： i=1: 5>1，不操作 i=2: 2 <5 → 增加到 6，操作次数=4 i=3: 4 <6 → 增加到 7，操作次数=4+3=7 i=4: 1 <7 → 增加到 8，操作次数=7+7=14 结果正确。 步骤 5：为什么贪心有效？ 因为只能增加不能减少，所以为了最小化操作次数，每个元素应尽可能小地增加，只要满足大于前一个元素即可。 因此，最优策略是： 操作次数累加 nums[i] - 原始值 。 步骤 6：算法实现 初始化 ops = 0 从 i = 1 到 n-1 ： 如果 nums[i] <= nums[i-1] ： diff = nums[i-1] + 1 - nums[i] ops += diff nums[i] = nums[i-1] + 1 返回 ops 步骤 7：复杂度分析 时间复杂度：O(n) 空间复杂度：O(1) 步骤 8：验证示例 例1： [1,1,1] i=1: 1≤1 → diff=1, ops=1, nums[ 1 ]=2 i=2: 1≤2 → diff=2, ops=3, nums[ 2 ]=3 ✅ 例2： [1,5,2,4,1] i=1: 5>1，不操作 i=2: 2<5 → diff=4, ops=4, nums[ 2 ]=6 i=3: 4<6 → diff=3, ops=7, nums[ 3 ]=7 i=4: 1<7 → diff=7, ops=14, nums[ 4 ]=8 ✅ 总结 本题通过贪心策略即可解决，核心是“每个元素只需增加到比前一个元素大 1”，从而保证操作次数最小。虽然题目归类为线性动态规划，但贪心解法更高效。