Question

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

English Version

题目描述

给定一个下标 从 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$ 的长度。

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))

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;
  }
}

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;
  }
};

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
}

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;
}