跳转至

3018. 可处理的最大删除操作数 I 🔒

题目描述

给定一个下标 从 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

解法

方法一：动态规划

我们定义 $f[i][j]$ 表示区间 $[i, j]$ 的数还没有被删除时，我们能够处理的查询的最大数量。

考虑 $f[i][j]$：

  • 如果 $i \gt 0$，此时 $f[i][j]$ 的值可以由 $f[i - 1][j]$ 转移而来。如果 $nums[i - 1] \ge queries[f[i - 1][j]]$，那么我们可以选择删除 $nums[i - 1]$，因此我们有 $f[i][j] = f[i - 1][j] + (nums[i - 1] \ge queries[f[i - 1][j]])$。
  • 如果 $j + 1 \lt n$，此时 $f[i][j]$ 的值可以由 $f[i][j + 1]$ 转移而来。如果 $nums[j + 1] \ge queries[f[i][j + 1]]$，那么我们可以选择删除 $nums[j + 1]$，因此我们有 $f[i][j] = f[i][j + 1] + (nums[j + 1] \ge queries[f[i][j + 1]])$。
  • 如果 $f[i][j] = m$，那么我们就可以直接返回 $m$。

最后的答案即为 $\max\limits_{0 \le i \lt n} f[i][i] + (nums[i] \ge queries[f[i][i]])$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 为数组 $nums$ 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumProcessableQueries(self, nums: List[int], queries: List[int]) -> int:
        n = len(nums)
        f = [[0] * n for _ in range(n)]
        m = len(queries)
        for i in range(n):
            for j in range(n - 1, i - 1, -1):
                if i:
                    f[i][j] = max(
                        f[i][j], f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]])
                    )
                if j + 1 < n:
                    f[i][j] = max(
                        f[i][j], f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]])
                    )
                if f[i][j] == m:
                    return m
        return max(f[i][i] + (nums[i] >= queries[f[i][i]]) for i in range(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maximumProcessableQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int[][] f = new int[n][n];
        int m = queries.length;
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= i; --j) {
                if (i > 0) {
                    f[i][j] = Math.max(
                        f[i][j], f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]] ? 1 : 0));
                }
                if (j + 1 < n) {
                    f[i][j] = Math.max(
                        f[i][j], f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]] ? 1 : 0));
                }
                if (f[i][j] == m) {
                    return m;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, f[i][i] + (nums[i] >= queries[f[i][i]] ? 1 : 0));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maximumProcessableQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        int f[n][n];
        memset(f, 0, sizeof(f));
        int m = queries.size();
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= i; --j) {
                if (i > 0) {
                    f[i][j] = max(f[i][j], f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]] ? 1 : 0));
                }
                if (j + 1 < n) {
                    f[i][j] = max(f[i][j], f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]] ? 1 : 0));
                }
                if (f[i][j] == m) {
                    return m;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, f[i][i] + (nums[i] >= queries[f[i][i]] ? 1 : 0));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func maximumProcessableQueries(nums []int, queries []int) (ans int) {
    n := len(nums)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    m := len(queries)
    for i := 0; i < n; i++ {
        for j := n - 1; j >= i; j-- {
            if i > 0 {
                t := 0
                if nums[i-1] >= queries[f[i-1][j]] {
                    t = 1
                }
                f[i][j] = max(f[i][j], f[i-1][j]+t)
            }
            if j+1 < n {
                t := 0
                if nums[j+1] >= queries[f[i][j+1]] {
                    t = 1
                }
                f[i][j] = max(f[i][j], f[i][j+1]+t)
            }
            if f[i][j] == m {
                return m
            }
        }
    }
    for i := 0; i < n; i++ {
        t := 0
        if nums[i] >= queries[f[i][i]] {
            t = 1
        }
        ans = max(ans, f[i][i]+t)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function maximumProcessableQueries(nums: number[], queries: number[]): number {
    const n = nums.length;
    const f: number[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
    const m = queries.length;
    for (let i = 0; i < n; ++i) {
        for (let j = n - 1; j >= i; --j) {
            if (i > 0) {
                f[i][j] = Math.max(
                    f[i][j],
                    f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]] ? 1 : 0),
                );
            }
            if (j + 1 < n) {
                f[i][j] = Math.max(
                    f[i][j],
                    f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]] ? 1 : 0),
                );
            }
            if (f[i][j] == m) {
                return m;
            }
        }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans = Math.max(ans, f[i][i] + (nums[i] >= queries[f[i][i]] ? 1 : 0));
    }
    return ans;
}

评论