Leetcode 3231. 要删除的递增子序列的最小数量

1.题目基本信息

1.1.题目描述

给定一个整数数组 nums，你可以执行任意次下面的操作：

• 从数组删除一个 严格递增 的 子序列。

您的任务是找到使数组为 空 所需的 最小 操作数。

1.2.题目地址

https://leetcode.cn/problems/minimum-number-of-increasing-subsequence-to-be-removed/description/

2.解题方法

2.1.解题思路

思路：二分查找

题目转换：等价于求最长非严格递减子序列的长度

2.2.解题步骤

第一步，构建维护变量。arr[i]维护长度为i的最长非严格递减子序列的最后一个元素的最大值；由于后续的arr尾部插入和二分插入的操作可知，arr一定是非严格单调递减的的。

第二步，循环遍历nums，得到nums[i]。如果nums[i]<=arr[-1]，将nums[i]添加到arr最后面；否则，将nums[i]插入到arr中，替换第一个小于nums[i]的元素arr[j]

• 2.1.二分不变量：arr[left-1]>=nums[i]恒成立，arr[right]<nums[i]恒成立；最终的right即为目标索引

第三步，最终的len(arr)-1即为题解

3.解题代码

python代码

# 思路2：动态规划class Solution:def minOperations(self, nums: List[int]) -> int:# 思路：题目转换：等价于求最长非严格递减子序列的长度# 第一步，构建维护变量。arr[i]维护长度为i的最长非严格递减子序列的最后一个元素的最大值；由于后续的arr尾部插入和二分插入的操作可知，arr一定是非严格单调递减的的。arr = [inf]# 第二步，循环遍历nums，得到nums[i]。如果nums[i]<=arr[-1]，将nums[i]添加到arr最后面；否则，将nums[i]插入到arr中，替换第一个小于nums[i]的元素arr[j]n = len(nums)for i in range(n):if nums[i] <= arr[-1]:arr.append(nums[i])else:# 2.1.二分不变量：arr[left-1]>=nums[i]恒成立，arr[right]<nums[i]恒成立；最终的right即为目标索引left, right = 1, len(arr)while left < right:mid = left + (right - left) // 2if arr[mid] >= nums[i]:left = mid + 1else:right = midindex = rightarr[index] = nums[i]# 第三步，最终的len(arr)-1即为题解return len(arr) - 1

4.执行结果