2070. 每一个查询的最大美丽值

🟠   🔖  数组 二分查找 排序  🔗 力扣 LeetCode

题目

You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an arrayanswer of the same length asquerieswhereanswer[j]is the answer to thejth query.

Example 1:

Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]

Output: [2,4,5,5,6,6]

Explanation:

• For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.

• For queries[1]=2, the items which can be considered are [1,2] and [2,4].

  The maximum beauty among them is 4.

• For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].

  The maximum beauty among them is 5.

• For queries[4]=5 and queries[5]=6, all items can be considered.

  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

Example 2:

Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]

Output: [4]

Explanation:

The price of every item is equal to 1, so we choose the item with the maximum beauty 4.

Note that multiple items can have the same price and/or beauty.

Example 3:

Input: items = [[10,1000]], queries = [5]

Output: [0]

Explanation:

No item has a price less than or equal to 5, so no item can be chosen.

Hence, the answer to the query is 0.

Constraints:

• 1 <= items.length, queries.length <= 10^5
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= 10^9

题目大意

给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。

同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。

请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。

示例 1：

输入： items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]

输出：[2,4,5,5,6,6]

解释：

• queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。

• queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。

  它们中的最大美丽值为 4 。

• queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。

  它们中的最大美丽值为 5 。

• queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。

  所以，答案为所有物品中的最大美丽值，为 6 。

示例 2：

输入： items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]

输出：[4]

解释：

每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。

注意，多个物品可能有相同的价格和美丽值。

示例 3：

输入： items = [[10,1000]], queries = [5]

输出：[0]

解释：

没有物品的价格小于等于 5 ，所以没有物品可以选择。

因此，查询的结果为 0 。

提示：

• 1 <= items.length, queries.length <= 10^5
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= 10^9

解题思路

1. 排序并预处理 items:
   • 首先将 items 按 price 从小到大排序。如果 price 相同，按 beauty 从大到小排序，这样可以保证同一 price 只记录最大 beauty 的物品。
2. 构建最大美丽值前缀数组:
   • 创建一个数组 maxBeautyArr，用来记录从 items[0] 开始到当前价格的最大美丽值。这样我们可以高效地获取所有价格小于等于某一价格的最大美丽值。
   • 遍历排序后的 items，将最大美丽值不断更新存储在这个数组中。
3. 对 queries 进行二分查找:
   • 将 queries 和其下标组合成元组并按 queries 升序排序。然后对每个查询 query，使用二分查找在 maxBeautyArr 中找到不超过 query 的最大价格的索引。
   • 根据找到的索引直接获得对应的最大美丽值。
4. 还原结果:
   • 将按顺序得到的答案放回原始 queries 的顺序中。

复杂度分析

• 时间复杂度：O((m + n) log m)。

  • 排序 items 需要 O(m log m) 时间复杂度，其中 m 是 items 的长度。
  • 预处理 maxBeautyArr 数组的时间复杂度为 O(m)。
  • queries 排序时间复杂度为 O(n log n)，其中 n 是 queries 的长度。
  • 对每个查询使用二分查找，遍历 queries 所需总时间复杂度为 O(n log m)。
  • 所以总体时间复杂度为 O((m + n) log m)。

• 空间复杂度：O(m + n)，排序所需的空间复杂度为 O(m + n)。

代码

/**
 * @param {number[][]} items
 * @param {number[]} queries
 * @return {number[]}
 */
var maximumBeauty = function (items, queries) {
	// 对 items 排序
	items.sort((a, b) => (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));

	// 找到每个 price 对应的最大 beauty
	let maxBeauty = 0,
		maxBeautyArr = [];

	for (let [price, beauty] of items) {
		maxBeauty = Math.max(maxBeauty, beauty);
		maxBeautyArr.push([price, maxBeauty]);
	}

	// 对 queries 进行排序
	const sortedQueries = queries
		.map((q, i) => [q, i])
		.sort((a, b) => a[0] - b[0]);
	let res = new Array(queries.length);
	let i = 0;
	for (let [query, idx] of sortedQueries) {
		// 移动 i 到小于等于 query 的最大 price
		while (i < maxBeautyArr.length && maxBeautyArr[i][0] <= query) {
			i++;
		}
		// 如果 i 为 0， 说明没有小于等于 query 的 price，返回 0
		res[idx] = i == 0 ? 0 : maxBeautyArr[i - 1][1];
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
1847	最近的房间		数组 二分查找 有序集合 1+	🔴	🀄️ 🔗
2640	一个数组所有前缀的分数		数组 前缀和	🟠	🀄️ 🔗
2736	最大和查询		栈 树状数组 线段树 4+	🔴	🀄️ 🔗