3231：要删除的递增子序列的最小数量（★★）

Ian

2024-07-26 约 224 字预计阅读 1 分钟次阅读

力扣第 3231 题

题目

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

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

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

示例 1：

输入：nums = [5,3,1,4,2]

输出：3

解释：

我们删除子序列 [1, 2]，[3, 4]，[5]。

示例 2：

输入：nums = [1,2,3,4,5]

输出：1

示例 3：

输入：nums = [5,4,3,2,1]

输出：5

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

分析

由 Dilworth 定理，等价于求最长不减的子序列
即是经典的 dp 问题

解答

1
2
3
4
5
6
7
8


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        A = nums[::-1]
        B = []
        for a in A:
            i = bisect_right(B,a)
            B[i:i+1] = [a]
        return len(B)

200 ms

目录

3231：要删除的递增子序列的最小数量（★★）

题目

分析

解答