2070.md

title	description	keywords
2070. 每一个查询的最大美丽值	LeetCode 2070. 每一个查询的最大美丽值题解，Most Beautiful Item for Each Query，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2070. 每一个查询的最大美丽值 每一个查询的最大美丽值 Most Beautiful Item for Each Query 解题思路 数组 二分查找 排序

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

🟠 Medium  🔖  数组 二分查找 排序  🔗 力扣 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 asqueries whereanswer[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+	🔴	🀄️ 🔗