使数组不减的最少操作次数
Minimum number of operations to make an array non-decreasing
你有一个整数数组。
只需一步，您就可以将任意索引处的值更改为任意整数值。
使数组不递减的最小步数是多少？
例如 1:
If the array is [8, 12, 11, 15],
We can change the value at the index 2 from 11 to 13. Then the array
becomes [8, 12, 13, 15]
So, no of steps needed = 1
例如 2:
If the array is [9, 2, 5, 18, 20, 25, 19],
We can change the value at the index 0 from 9 to 2 and the value at the index 6 from 19 to 30. Then the array
becomes [2, 2, 5, 18, 20, 25, 30]
So, no of steps needed = 2
例如 3:
If the array is [9, 11, 5, 7],
We can change the value at the index 2 from 5 to 11 and the value at the index 3 from 7 to 11. Then the array
becomes [9, 11, 11, 11]
So, no of steps needed = 2
例如 4:
If the array is [13, 12, 10, 7, 6],
After making the changes, the array becomes [13, 13, 13, 13, 13] or [6, 7, 10, 12, 13]. There are multiple ways of doing this.
So, no of steps needed = 4
我尝试过的一种方法是找到所有递减的子序列并将 length of them - 1 添加到名为 ans 的变量中。那就return吧。但它在上面提到的 Eg 3 中失败了。
如何解决？
我觉得这道题相当于求序列中最长的非递减链
将每个索引i作为图的节点。那么当且仅当 i < j 且 L[i] <= L[j] 时，节点 i 有指向节点 j 的箭头。然后你需要使用图论中的技术找到图中最长的路径。
由于条件 i，您不会得到循环
正如所说，这相当于找到最长的非递减子序列。
如果在输入数组A中找到任何非递减子序列S，则只取[=中剩余元素的值45=]A需要改成让整个数组不减。要更改的元素个数为|A| - |S|.
如果该子序列是最长非递减子序列，它为您提供了最大数量的已经排序的元素，那么要更改的元素数量，| 一个| - |S|, 将被最小化。如果您选择任何较短的非递减子序列，则需要更改更多元素。
您可以使用 Patience sorting 找到该子序列的长度。
来自维基百科的算法：
- 发的第一张牌形成一个由单张牌组成的新牌堆。
- 随后的每张牌都放在某个现有牌堆上，其顶牌的价值不低于新牌的价值，或者放在所有现有牌堆的右边，从而形成一个新牌堆。
- 当没有剩余牌可发时，游戏结束。
使用您的示例 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).
您可以在此处找到关于 Patience 排序在查找最长递增子序列中正确性的讨论和参考：
Why does Patience sorting find the longest increasing subsequence?
你有一个整数数组。
只需一步，您就可以将任意索引处的值更改为任意整数值。 使数组不递减的最小步数是多少？
例如 1:
If the array is [8, 12, 11, 15],
We can change the value at the index 2 from 11 to 13. Then the array becomes [8, 12, 13, 15]
So, no of steps needed = 1
例如 2:
If the array is [9, 2, 5, 18, 20, 25, 19],
We can change the value at the index 0 from 9 to 2 and the value at the index 6 from 19 to 30. Then the array becomes [2, 2, 5, 18, 20, 25, 30]
So, no of steps needed = 2
例如 3:
If the array is [9, 11, 5, 7],
We can change the value at the index 2 from 5 to 11 and the value at the index 3 from 7 to 11. Then the array becomes [9, 11, 11, 11]
So, no of steps needed = 2
例如 4:
If the array is [13, 12, 10, 7, 6],
After making the changes, the array becomes [13, 13, 13, 13, 13] or [6, 7, 10, 12, 13]. There are multiple ways of doing this.
So, no of steps needed = 4
我尝试过的一种方法是找到所有递减的子序列并将 length of them - 1 添加到名为 ans 的变量中。那就return吧。但它在上面提到的 Eg 3 中失败了。
如何解决？
我觉得这道题相当于求序列中最长的非递减链
将每个索引i作为图的节点。那么当且仅当 i < j 且 L[i] <= L[j] 时，节点 i 有指向节点 j 的箭头。然后你需要使用图论中的技术找到图中最长的路径。
由于条件 i
正如
如果在输入数组A中找到任何非递减子序列S，则只取[=中剩余元素的值45=]A需要改成让整个数组不减。要更改的元素个数为|A| - |S|.
如果该子序列是最长非递减子序列，它为您提供了最大数量的已经排序的元素，那么要更改的元素数量，| 一个| - |S|, 将被最小化。如果您选择任何较短的非递减子序列，则需要更改更多元素。
您可以使用 Patience sorting 找到该子序列的长度。
来自维基百科的算法：
- 发的第一张牌形成一个由单张牌组成的新牌堆。
- 随后的每张牌都放在某个现有牌堆上，其顶牌的价值不低于新牌的价值，或者放在所有现有牌堆的右边，从而形成一个新牌堆。
- 当没有剩余牌可发时，游戏结束。
使用您的示例 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).
您可以在此处找到关于 Patience 排序在查找最长递增子序列中正确性的讨论和参考： Why does Patience sorting find the longest increasing subsequence?