使数组非递减的最少操作次数

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 我尝试的一种方法是找到所有下降子序列，并将它们的长度 -1 添加到名为 ans 的变量中。然后返回它。但是这在上述第三个示例中失败了。 如何解决？

- Light Yagami

---

你尝试过将这个问题建模成图，然后使用广度优先搜索吗？你可以为每个操作创建边，其中包括将一个值扩大到前一个值或将一个值减小到后一个值的情况。 - Ulrich Eckhardt

你能发原始问题链接吗？这样我们就可以测试我们的解决方案。 - Ch3steR

@Ch3steR 抱歉，我没有链接。我的一个朋友问过我，但他现在没有回应。我尝试了一段时间，编写了代码，一些测试用例相互矛盾，我已经在这里提到了它们。 - Light Yagami

@UlrichEckhardt 没有，我没有尝试过。但这真的必要吗？我的意思是，不能只涉及数组遍历来更轻松地完成这个任务吗？ - Light Yagami

我不知道是否必需。根据我的经验，使用基于图形的方法来思考这个问题是一个很好的开始。也许这样做，你会发现一种导致更简单的解决方案的模式？无论如何，把它作为一个图形来考虑并不意味着你必须在代码中创建一个图形。通常，特别是使用BFS时，您可以从队列中的初始值开始，然后在弹出时将新的中间值添加到队列中，因此图形只是暗示而已。这可能需要额外的思考，例如避免进入循环，但它是可行的。 - Ulrich Eckhardt

Answer 1

如@sfx所述，这等同于寻找最长的非降子序列。

如果您在输入数组A中找到任何非降子序列S，则只需要更改A中其余元素的值即可使整个数组成为非降序列。需要更改的元素数量为|A| - |S|。

如果该子序列是最长的非降子序列，即给出了已经排序的最大元素数量，则要更改的元素数量|A| - |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)。 您可以在这里找到有关正确性的讨论和参考文献：为什么耐心排序能找到最长递增子序列？

- beaker

Answer 2

我认为这个问题等价于在序列中找到最长的非递减链。

将每个索引i视为图的节点。那么当且仅当i＜j且L[i]≤L[j]时，节点i向节点j有一个箭头。然后使用图论技术查找图中的最长路径。

由于条件i＜j，因此不会出现循环。

- sfx