bea*_*ker 7
正如@sfx提到的，这相当于找到最长的非递减子序列。
如果在输入数组A中找到任何非递减子序列S ，则只需更改A中剩余元素的值即可使整个数组不递减。要更改的元素数是| 一个| - | 小号|。
如果该子序列是最长的非递减子序列，它为您提供了最大数量的已排序的元素，那么要更改的元素数量，| 一个| - | S |, 将被最小化。如果您选择了任何较短的非递减子序列，则需要更改更多元素。
您可以使用耐心排序找到此子序列的长度。
来自维基百科的算法：
发的第一张牌形成一个由单张牌组成的新牌堆。 随后的每张牌都放在某个现有牌堆上，其顶牌的值不低于新牌的值，或者放在所有现有牌堆的右侧，从而形成一个新牌堆。 当没有剩余的牌可以处理时，游戏结束。使用您的示例 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)。
您可以在这里找到关于耐心排序在寻找最长递增子序列中的正确性的讨论和参考： 为什么耐心排序会找到最长递增子序列？
更多推荐
数组,最小,操作
发布评论