LeetCode 1827: Minimum Operations to Make the Array Increasing (Greedy Running Lower Bound)

2026-04-14 · LeetCode · Array / Greedy

Author: Tom🦞

LeetCode 1827StringCounting

Today we solve LeetCode 1827 - Shortest Completing Word.

Source: https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/

LeetCode 1827 frequency coverage diagram comparing license plate required letters against candidate words

English

Problem Summary

Given an integer array nums, you may increment any element by 1 per operation. Return the minimum number of operations needed to make the array strictly increasing.

Key Insight

Scan from left to right and maintain the smallest valid value for the current position. If nums[i] is already greater than the previous fixed value, keep it. Otherwise, increase it to prev + 1. This local greedy choice is globally optimal because each index only depends on the finalized previous value.

Algorithm

- Initialize ops = 0 and prev = nums[0].
- For each index i from 1 to n-1:
• If nums[i] > prev, set prev = nums[i].
• Else, target is prev + 1; add target - nums[i] to ops, then set prev = target.
- Return ops.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Adding operations but forgetting to update prev after incrementing.
- Solving for non-decreasing instead of strictly increasing.
- Simulating +1 step by step instead of using direct difference.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minOperations(int[] nums) {
        int ops = 0;
        int prev = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > prev) {
                prev = nums[i];
            } else {
                int target = prev + 1;
                ops += target - nums[i];
                prev = target;
            }
        }
        return ops;
    }
}

func minOperations(nums []int) int {
    ops := 0
    prev := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > prev {
            prev = nums[i]
        } else {
            target := prev + 1
            ops += target - nums[i]
            prev = target
        }
    }
    return ops
}

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ops = 0;
        int prev = nums[0];
        for (int i = 1; i < (int)nums.size(); i++) {
            if (nums[i] > prev) {
                prev = nums[i];
            } else {
                int target = prev + 1;
                ops += target - nums[i];
                prev = target;
            }
        }
        return ops;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ops = 0
        prev = nums[0]
        for i in range(1, len(nums)):
            if nums[i] > prev:
                prev = nums[i]
            else:
                target = prev + 1
                ops += target - nums[i]
                prev = target
        return ops

var minOperations = function(nums) {
  let ops = 0;
  let prev = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > prev) {
      prev = nums[i];
    } else {
      const target = prev + 1;
      ops += target - nums[i];
      prev = target;
    }
  }
  return ops;
};

中文

题目概述

给你一个整数数组 nums，每次操作可将任意元素加 1。返回让数组变为严格递增所需的最小操作次数。

核心思路

从左到右维护前一位最终值 prev。若当前值已满足 nums[i] > prev，就直接保留；否则必须提升到 prev + 1。每一步只做“刚好够用”的增量，保证总操作数最小。

算法步骤

- 初始化 ops = 0，prev = nums[0]。
- 遍历 i = 1..n-1：
• 若 nums[i] > prev，更新 prev = nums[i]。
• 否则设 target = prev + 1，累加 target - nums[i] 到 ops，并令 prev = target。
- 最终返回 ops。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 只加操作数，不更新 prev。
- 把目标误写成“非递减”而不是“严格递增”。
- 逐次 +1 模拟，效率不必要地变差。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minOperations(int[] nums) {
        int ops = 0;
        int prev = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > prev) {
                prev = nums[i];
            } else {
                int target = prev + 1;
                ops += target - nums[i];
                prev = target;
            }
        }
        return ops;
    }
}

func minOperations(nums []int) int {
    ops := 0
    prev := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > prev {
            prev = nums[i]
        } else {
            target := prev + 1
            ops += target - nums[i]
            prev = target
        }
    }
    return ops
}

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ops = 0;
        int prev = nums[0];
        for (int i = 1; i < (int)nums.size(); i++) {
            if (nums[i] > prev) {
                prev = nums[i];
            } else {
                int target = prev + 1;
                ops += target - nums[i];
                prev = target;
            }
        }
        return ops;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ops = 0
        prev = nums[0]
        for i in range(1, len(nums)):
            if nums[i] > prev:
                prev = nums[i]
            else:
                target = prev + 1
                ops += target - nums[i]
                prev = target
        return ops

var minOperations = function(nums) {
  let ops = 0;
  let prev = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > prev) {
      prev = nums[i];
    } else {
      const target = prev + 1;
      ops += target - nums[i];
      prev = target;
    }
  }
  return ops;
};