使数组不减的最少操作次数

Question

你有一个整数数组。

您只需一步即可将任意索引处的值更改为任意整数值。可以使数组不减的最少步数是多少？

例如1：

如果数组是 [8, 12, 11, 15]，

我们可以将索引 2 处的值从 11 更改为 13。然后数组变为 [8, 12, 13, 15]

因此，所需步骤数 = 1

例如2：

如果数组是 [9, 2, 5, 18, 20, 25, 19]，

我们可以将索引 0 处的值从 9 更改为 2，将索引 6 处的值从 19 更改为 30。那么数组就变成了 [2, 2, 5, 18, 20, 25, 30]

因此，所需步骤数 = 2

例如3：

如果数组是 [9, 11, 5, 7]，

我们可以将索引 2 处的值从 5 更改为 11，将索引 3 处的值从 7 更改为 11。那么数组就变成了 [9, 11, 11, 11]

因此，所需步骤数 = 2

例如4：

如果数组是 [13, 12, 10, 7, 6]，

进行更改后，数组变为 [13, 13, 13, 13, 13] 或 [6, 7, 10, 12, 13]。有多种方法可以做到这一点。

因此，所需步骤数 = 4

我尝试的一种方法是找到所有递减子序列并将其添加length of them - 1到名为 的变量中ans。然后返回它。但它在上面提到的 Eg 3 中失败了。怎么解决这个问题呢？

Answer 1

正如@sfx提到的，这相当于找到最长的非递减子序列。

如果在输入数组A中发现任何非递减子序列S ，则只需更改A中剩余元素的值即可使整个数组非递减。要更改的元素数量是 | 一个| - | S |。

如果该子序列是最长的非递减子序列，它为您提供了已排序顺序的最大元素数，则要更改的元素数 | 一个| - | S |，将被最小化。如果您选择任何较短的非递减子序列，则需要更改更多元素。

您可以使用耐心排序找到该子序列的长度。

维基百科的算法：

1. 发出的第一张牌形成由单张牌组成的新牌堆。
2. 随后的每张牌都放置在某个现有牌堆上，其顶牌的值不小于新牌的值，或者放置在所有现有牌堆的右侧，从而形成新的牌堆。
3. 当没有更多的牌可供发时，游戏结束。

使用你的例子3：

[9, 11, 5, 7]

插入[9]：

[9]

插入[11]：输出数组中没有大于等于[11]的值，所以再添加一个栈：

[9, 11]

插入[5]：第一个大于或等于[5]的值是[9]，所以替换[9]：

[5, 11]

插入[7]：第一个大于或等于[7]的值为[11]，替换[11]：

[5, 7]

输出数组的长度是最长非递减子序列的长度。使整个序列不减的操作次数等于输入数组中的元素数量减去该子序列的长度。

使用二分搜索来确定放置下一个值的位置，此方法最坏情况的时间复杂度为O(n log n)。

您可以在此处找到有关耐心排序在查找最长递增子序列时的正确性的讨论和参考： 为什么耐心排序会查找最长递增子序列？