minimum-number-of-increments-on-subarrays-to-form-a-target-array

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 an integer array <code>target</code>. You have an integer array <code>initial</code> of the same size as <code>target</code> with all elements initially zeros.

In one operation you can choose any subarray from <code>initial</code> and increment each value by one.

Return the minimum number of operations to form a <code>target</code> array from <code>initial</code>.

The test cases are generated so that the answer fits in a 32-bit integer.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
Input: target = [3,1,1,2]
Output: 4
Explanation: [0,0,0,0] -&gt; [1,1,1,1] -&gt; [1,1,1,2] -&gt; [2,1,1,2] -&gt; [3,1,1,2]
</pre>

Example 3:

<pre>
Input: target = [3,1,5,4,2]
Output: 7
Explanation: [0,0,0,0,0] -&gt; [1,1,1,1,1] -&gt; [2,1,1,1,1] -&gt; [3,1,1,1,1] -&gt; [3,1,2,2,2] -&gt; [3,1,3,3,2] -&gt; [3,1,4,4,2] -&gt; [3,1,5,4,2].
</pre>

&nbsp;
Constraints:

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

minNumberOperations

Minimum Number of Increments on Subarrays to Form a Target Array

Stack

Greedy

Array

Dynamic Programming

Monotonic Stack

给你一个整数数组&nbsp;<code>target</code>&nbsp;和一个数组&nbsp;<code>initial</code>&nbsp;，<code>initial</code>&nbsp;数组与 <code>target</code>&nbsp; 数组有同样的维度，且一开始全部为 0 。

请你返回从 <code>initial</code>&nbsp;得到&nbsp; <code>target</code>&nbsp;的最少操作次数，每次操作需遵循以下规则：

<ul>
	<li>在 <code>initial</code>&nbsp;中选择 任意&nbsp;子数组，并将子数组中每个元素增加 1 。</li>
</ul>

答案保证在 32 位有符号整数以内。

&nbsp;

示例 1：

<pre>输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4&nbsp;的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。
</pre>

示例 2：

<pre>输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -&gt; [1,1,1,1] -&gt; [1,1,1,2] -&gt; [2,1,1,2] -&gt; [3,1,1,2] (target) 。
</pre>

示例 3：

<pre>输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -&gt; [1,1,1,1,1] -&gt; [2,1,1,1,1] -&gt; [3,1,1,1,1] 
 -&gt; [3,1,2,2,2] -&gt; [3,1,3,3,2] -&gt; [3,1,4,4,2] -&gt; [3,1,5,4,2] (target)。
</pre>

示例 4：

<pre>输入：target = [1,1,1,1]
输出：1
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= target.length &lt;= 10^5</code></li>
	<li><code>1 &lt;= target[i] &lt;= 10^5</code></li>
</ul>