3018：可处理的最大删除操作数 I（★★）

力扣第 3018 题

题目

给定一个下标 从 0 开始 的数组 nums 和一个下标 从 0 开始 的数组 queries。

你可以在开始时执行以下操作 最多一次：

• 用 nums 的 子序列 替换 nums。

我们以给定的queries顺序处理查询；对于queries[i]，我们执行以下操作：

• 如果 nums 的第一个 和 最后一个元素 小于 queries[i]，则查询处理 结束。
• 否则，从 nums 选择第一个 或 最后一个元素，要求其大于或等于 queries[i]，然后将其从 nums 中 删除。

返回通过以最佳方式执行该操作可以处理的 最多 次数。

示例 1：

输入：nums = [1,2,3,4,5], queries = [1,2,3,4,6]
输出：4
解释：我们不执行任何操作，并按如下方式处理查询：
1- 我们选择并移除 nums[0]，因为 1 <= 1，那么 nums 就变成 [2,3,4,5]。
2- 我们选择并移除 nums[0]，因为 2 <= 2，那么 nums 就变成 [3,4,5]。
3- 我们选择并移除 nums[0]，因为 3 <= 3，那么 nums 就变成 [4,5]。
4- 我们选择并移除 nums[0]，因为 4 <= 4，那么 nums 就变成 [5]。
5- 我们不能从 nums 中选择任何元素，因为它们不大于或等于 5。
因此，答案为 4。
可以看出，我们不能处理超过 4 个查询。

示例 2：

输入：nums = [2,3,2], queries = [2,2,3]
输出：3
解释：我们不做任何操作，按如下方式处理查询：
1- 我们选择并移除 nums[0]，因为 2 <= 2，那么 nums 就变成 [3,2]。
2- 我们选择并移除 nums[1]，因为 2 <= 2，那么 nums 就变成 [3]。
3- 我们选择并移除 nums[0]，因为 3 <= 3，那么 nums 就变成 []。
因此，答案为 3。
可以看出，我们不能处理超过 3 个查询。

示例 3：

输入：nums = [3,4,3], queries = [4,3,2]
输出：2
解释：首先，我们用 nums 的子序列 [4,3] 替换 nums。
然后，我们可以按如下方式处理查询：
1- 我们选择并移除 nums[0]，因为 4 <= 4，那么 nums 就变成 [3]。
2- 我们选择并移除 nums[0]，因为 3 <= 3，那么 nums 就变成 []。
3- 我们无法处理更多查询，因为 nums 为空。
因此，答案为 2。
可以看出，我们不能处理超过 2 个查询。

提示：

• 1 <= nums.length <= 1000
• 1 <= queries.length <= 1000
• 1 <= nums[i], queries[i] <= 109

分析

• 为了方便，令 A=nums, B=A[::-1]
• 令 f[i][j] 代表用 A[:i] 和 B[:j] 能处理的最大次数
• 按最后由谁处理即可递推
• 注意保证 i+j<=n

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def maximumProcessableQueries(self, nums: List[int], queries: List[int]) -> int:
        n = len(nums)
        m = len(queries)
        A,B = nums,nums[::-1]
        f = [[0]*(n-i+1) for i in range(n+1)]
        for i in range(n+1):
            for j in range(n-i+1):
                if i:
                    a = f[i-1][j]
                    f[i][j] = a+(A[i-1]>=queries[a])
                if j:
                    b = f[i][j-1]
                    f[i][j] = max(f[i][j],b+(B[j-1]>=queries[b]))
                if f[i][j]==m:
                    return m
        return max(sub[-1] for sub in f)

3458 ms