1526. Minimum Number of Increments on Subarrays to Form a Target Array

Given an array of positive integers target and an array initial of same size with all zeros.

Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

• Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.

Example 1:

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:

Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).

Example 3:

Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).

Example 4:

Input: target = [1,1,1,1]
Output: 1

Constraints:

• 1 <= target.length <= 10^5

• 1 <= target[i] <= 10^5

Solution

Intuition :

Focus on one element, we need to takes nums[i] ops to make it become 0. For it's next element nums[i+1], there are only 2 possiblilities:

• nums[i+1] > nums[i], that means nums[i+1] will take extra (nums[i+1] - num[i]) opertaions

• nums[i+1] <= num[i], it can be done on the way, when changing nums[i] to 0

• The diff to prev words

  • We want each num become zero

  • For first num, it needs at least num value's op to become 0

  • For the second number, if it is greater, it needs diff (current-prev) ops to become 0

  • If the Second num is less then first one, it needs 0 op, because it's op can be covered by first one

  • So we just need to sum up the diff between current one and prev one, if it is positive

    public int minNumberOperations(int[] target) {
        int count = 0, prev = 0;
        for(int a : target){
            count += Math.max(a-prev, 0);
            prev = a;
        }
        return count;
    }