minimum-pair-removal-to-sort-array-i

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array <code>nums</code>, you can perform the following operation any number of times:

<ul>
	<li>Select the adjacent pair with the minimum sum in <code>nums</code>. If multiple such pairs exist, choose the leftmost one.</li>
	<li>Replace the pair with their sum.</li>
</ul>

Return the minimum number of operations needed to make the array non-decreasing.

An array is said to be non-decreasing if each element is greater than or equal to its previous element (if it exists).

&nbsp;
Example 1:

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

Output: 2

Explanation:

<ul>
	<li>The pair <code>(3,1)</code> has the minimum sum of 4. After replacement, <code>nums = [5,2,4]</code>.</li>
	<li>The pair <code>(2,4)</code> has the minimum sum of 6. After replacement, <code>nums = [5,6]</code>.</li>
</ul>

The array <code>nums</code> became non-decreasing in two operations.
</div>

Example 2:

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

Output: 0

Explanation:

The array <code>nums</code> is already sorted.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 50</code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
</ul>

minimumPairRemoval

Minimum Pair Removal to Sort Array I

Array

Hash Table

Linked List

Doubly-Linked List

Ordered Set

Simulation

Heap (Priority Queue)

给你一个数组 <code>nums</code>，你可以执行以下操作任意次数：

<ul>
	<li>选择 相邻&nbsp;元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。</li>
	<li>用它们的和替换这对元素。</li>
</ul>

返回将数组变为&nbsp;非递减&nbsp;所需的&nbsp;最小操作次数&nbsp;。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

&nbsp;

示例 1：

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

输出： 2

解释：

<ul>
	<li>元素对 <code>(3,1)</code> 的和最小，为 4。替换后&nbsp;<code>nums = [5,2,4]</code>。</li>
	<li>元素对 <code>(2,4)</code> 的和为 6。替换后&nbsp;<code>nums = [5,6]</code>。</li>
</ul>

数组 <code>nums</code> 在两次操作后变为非递减。
</div>

示例 2：

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

输出： 0

解释：

数组 <code>nums</code> 已经是非递减的。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 50</code></li>
	<li><code>-1000&nbsp;&lt;= nums[i] &lt;= 1000</code></li>
</ul>