将数组调整为非递减序列所需的最少操作次数求解方法

核心结论 #

这个问题的解法非常直接：最少操作次数 = 数组总长度 - 数组的最长非递减子序列（非严格递增）的长度。

原思路错误原因 #

你之前统计所有递减子序列长度减1累加的思路，本质是只关注相邻的递减破坏点，没有考虑到我们可以不连续保留原数组元素，只要保留的元素相对顺序不变、且本身是非递减的，就可以不用修改。
比如示例3的数组[9,11,5,7]，你可以保留[9,11]两个元素，剩下两个元素修改为大于等于11的数即可，不需要额外处理5和7本身的递增关系。

解法原理 #

我们要最小化修改次数，等价于最大化不需要修改的元素数量，而不需要修改的元素必须满足两个条件：

1. 相对顺序和原数组完全一致
2. 元素本身是非递减的
   满足条件的最长序列就是最长非递减子序列，剩下的元素都可以通过修改适配这个保留序列，得到合法的非递减数组。

实现方案 #

复杂度说明 #

• 普通动态规划实现：时间复杂度O(n²)，适合小规模数据
• 贪心+二分优化实现：时间复杂度O(nlogn)，适合大规模数据

代码示例（Python） #

import bisect

def min_modify_operations(nums):
    # 计算最长非递减子序列的长度
    tails = []
    for num in nums:
        # 非递增匹配用bisect_right，严格递增匹配换bisect_left
        idx = bisect.bisect_right(tails, num)
        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num
    return len(nums) - len(tails)

示例验证 #

• 示例1数组[8,12,11,15]：最长非递减子序列长度3，4-3=1，结果正确
• 示例2数组[9,2,5,18,20,25,19]：最长非递减子序列长度5，7-5=2，结果正确
• 示例3数组[9,11,5,7]：最长非递减子序列长度2，4-2=2，结果正确
• 示例4数组[13,12,10,7,6]：最长非递减子序列长度1，5-1=4，结果正确

内容的提问来源于stack exchange，提问作者Light Yagami