minimum-operations-to-make-array-equal-to-target

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two positive integer arrays <code>nums</code> and <code>target</code>, of the same length.

In a single operation, you can select any subarray of <code>nums</code> and increment each element within that subarray by 1 or decrement each element within that subarray by 1.

Return the minimum number of operations required to make <code>nums</code> equal to the array <code>target</code>.

&nbsp;
Example 1:

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

Output: 2

Explanation:

We will perform the following operations to make <code>nums</code> equal to <code>target</code>: 
- Increment&nbsp;<code>nums[0..3]</code> by 1, <code>nums = [4,6,2,3]</code>. 
- Increment&nbsp;<code>nums[3..3]</code> by 1, <code>nums = [4,6,2,4]</code>.
</div>

Example 2:

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

Output: 5

Explanation:

We will perform the following operations to make <code>nums</code> equal to <code>target</code>: 
- Increment&nbsp;<code>nums[0..0]</code> by 1, <code>nums = [2,3,2]</code>. 
- Decrement&nbsp;<code>nums[1..1]</code> by 1, <code>nums = [2,2,2]</code>. 
- Decrement&nbsp;<code>nums[1..1]</code> by 1, <code>nums = [2,1,2]</code>. 
- Increment&nbsp;<code>nums[2..2]</code> by 1, <code>nums = [2,1,3]</code>. 
- Increment&nbsp;<code>nums[2..2]</code> by 1, <code>nums = [2,1,4]</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length == target.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i], target[i] &lt;= 108</code></li>
</ul>

minimumOperations

Minimum Operations to Make Array Equal to Target

Stack

Greedy

Array

Dynamic Programming

Monotonic Stack

给你两个长度相同的正整数数组 <code>nums</code> 和 <code>target</code>。

在一次操作中，你可以选择 <code>nums</code> 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。

返回使 <code>nums</code> 数组变为 <code>target</code> 数组所需的 最少 操作次数。

&nbsp;

示例 1：

<div class="example-block">
输入： nums = [3,5,1,2], target = [4,6,2,4]

输出： 2

解释：

执行以下操作可以使 <code>nums</code> 等于 <code>target</code>： 
- <code>nums[0..3]</code> 增加 1，<code>nums = [4,6,2,3]</code>。 
- <code>nums[3..3]</code> 增加 1，<code>nums = [4,6,2,4]</code>。
</div>

示例 2：

<div class="example-block">
输入： nums = [1,3,2], target = [2,1,4]

输出： 5

解释：

执行以下操作可以使 <code>nums</code> 等于 <code>target</code>： 
- <code>nums[0..0]</code> 增加 1，<code>nums = [2,3,2]</code>。 
- <code>nums[1..1]</code> 减少 1，<code>nums = [2,2,2]</code>。 
- <code>nums[1..1]</code> 减少 1，<code>nums = [2,1,2]</code>。 
- <code>nums[2..2]</code> 增加 1，<code>nums = [2,1,3]</code>。 
- <code>nums[2..2]</code> 增加 1，<code>nums = [2,1,4]</code>。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length == target.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i], target[i] &lt;= 108</code></li>
</ul>