2. Minimum Operations to Make an Array Strictly Increasing

1. Description

You are given an array nums containing n positive integers.
In one operation, you may choose a contiguous subarray nums[l…r] and a positive integer x, and add x to every element in that subarray.
An array is strictly increasing if nums[i] < nums[i+1] for every valid index i.
Return the minimum number of operations required to make nums strictly increasing.

2. Solution

n = A.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int solution(const vector<int> &A) {
    int count = 0;

    for (int i = 1; i < A.size(); ++i) {
        if (A[i] <= A[i - 1]) {
            ++count;
        }
    }

    return count;
}