minimum-operations-to-make-array-non-decreasing

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code> of length <code>n</code>.

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

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

An array is non-decreasing if <code>nums[i] &lt;= nums[i + 1]</code> for all <code>0 &lt;= i &lt; n - 1</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [3,3,2,1]

Output: 2

Explanation:

One optimal set of operations:

<ul>
	<li>Choose subarray <code>[2..3]</code> and add <code>x = 1</code> resulting in <code>[3, 3, 3, 2]</code></li>
	<li>Choose subarray <code>[3..3]</code> and add <code>x = 1</code> resulting in <code>[3, 3, 3, 3]</code></li>
</ul>

The array becomes non-decreasing, and the total sum of chosen <code>x</code> values is <code>1 + 1 = 2</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [5,1,2,3]

Output: 4

Explanation:

One optimal set of operations:

<ul>
	<li>Choose subarray <code>[1..3]</code> and add <code>x = 4</code> resulting in <code>[5, 5, 6, 7]</code></li>
</ul>

The array becomes non-decreasing, and the total sum of chosen <code>x</code> values is <code>4</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

Weekly Contest 499

weekly-contest-499

minOperations

Staff

Minimum Operations to Make Array Non Decreasing

Array

Greedy

Accepted

Wrong Answer

Memory Limit Exceeded

Output Limit Exceeded

Time Limit Exceeded

Runtime Error

Internal Error

Compile Error

Timeout

Restrictions Failed

cangjie

react

vanillajs

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:

Input: nums = [3,3,2,1]

Output: 2

Explanation:

One optimal set of operations:

 * Choose subarray [2..3] and add x = 1 resulting in [3, 3, 3, 2]
 * Choose subarray [3..3] and add x = 1 resulting in [3, 3, 3, 3]

The array becomes non-decreasing, and the total sum of chosen x values is 1 + 1 = 2.

Example 2:

Input: nums = [5,1,2,3]

Output: 4

Explanation:

One optimal set of operations:

 * Choose subarray [1..3] and add x = 4 resulting in [5, 5, 6, 7]

The array becomes non-decreasing, and the total sum of chosen x values is 4.

 

Constraints:

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