3914. Minimum Operations to Make Array Non Decreasing

中文文档

Description

You are given an integer array nums of length n.

In one operation, you may choose any subarray nums[l..r] and increase each element in that subarray by x, where x is any positive integer.

Return the minimum possible sum of the values of x across all operations required to make the array non-decreasing.

An array is non-decreasing if nums[i] <= nums[i + 1] for all 0 <= i < n - 1.

 

Example 1:

Example 2:

 

Constraints:

• 1 <= n == nums.length <= 105
• 1 <= nums[i] <= 109

Solutions

Solution 1: Greedy

We can traverse the array from left to right and calculate the difference between each pair of adjacent elements. If the current element is smaller than the previous one, we need to increase the current element so that it is at least equal to the previous element. The amount to increase is the difference between the previous element and the current element.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

Python3

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        return sum(max(a - b, 0) for a, b in pairwise(nums))

Java

class Solution {
    public long minOperations(int[] nums) {
        long ans = 0;
        for (int i = 1; i < nums.length; ++i) {
            ans += Math.max(nums[i - 1] - nums[i], 0);
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long minOperations(vector<int>& nums) {
        long long ans = 0;
        for (int i = 1; i < nums.size(); ++i) {
            ans += max(nums[i - 1] - nums[i], 0);
        }
        return ans;
    }
};

Go

func minOperations(nums []int) (ans int64) {
	for i := 1; i < len(nums); i++ {
		ans += max(int64(nums[i-1]-nums[i]), 0)
	}
	return
}

TypeScript

function minOperations(nums: number[]): number {
    let ans = 0;
    for (let i = 1; i < nums.length; ++i) {
        ans += Math.max(nums[i - 1] - nums[i], 0);
    }
    return ans;
}