每一个查询的最大美丽值

标签: 数组 二分查找 排序

难度: Medium

给你一个二维整数数组 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 <= 105
  • items[i].length == 2
  • 1 <= pricei, beautyi, queries[j] <= 109

Submission

运行时间: 164 ms

内存: 63.3 MB

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort(key=itemgetter(0))
        mx = [*accumulate((l[1] for l in items), max, initial=0)]
        items = [l[0] for l in items]
        return [mx[bisect_right(items, q)] for q in queries]

Explain

此题解采用了排序和二分搜索的方法来处理查询。首先，将items数组按照价格排序。随后，使用accumulate函数生成一个新的列表mx，其中mx[i]表示所有价格不超过items[i][0]的物品中的最大美丽值。这样做的目的是为每个价格点快速找到其对应的最大美丽值。对于每个查询，使用bisect_right在排序后的价格列表items中找出最大的索引，该索引对应的价格不超过查询值。最后，根据这个索引在mx中找到答案。

时间复杂度: O(n log n + m log n)

空间复杂度: O(n)

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        # 对items按照价格进行排序
        items.sort(key=itemgetter(0))
        # 使用accumulate计算不超过当前价格的最大美丽值
        mx = [*accumulate((l[1] for l in items), max, initial=0)]
        # 提取排序后的价格列表
        items = [l[0] for l in items]
        # 对每个查询，利用二分查找确定不超过查询价格的最大美丽值的位置
        return [mx[bisect_right(items, q)] for q in queries]

Explore

是的，对items数组进行排序后，需要保持每个价格对应的美丽值不变。在排序过程中，每个元素（价格，美丽值对）被视为一个整体，排序仅改变它们在数组中的位置，而不改变价格和美丽值之间的关联。这样排序后，我们可以按价格顺序处理美丽值的累积最大值。

在此题目中，选择max作为累积函数是为了在给定价格范围内找到最大的美丽值。因为我们需要得到不超过某个价格的所有物品中的最大美丽值，使用max可以确保每步都取到目前为止遇到的最大美丽值。理论上，也可以通过手动比较和更新最大值来替代使用accumulate和max，但这将使代码更加复杂且容易出错。使用accumulate和max是一种更简洁和有效的方式。

bisect_right函数用于在已排序的列表中找到一个元素的插入点，使得插入后列表仍保持有序。在此题目中，它用来找到一个查询价格应该插入的位置索引，这个位置索引表示所有价格不超过查询价格的物品。在价格相同的情况下，bisect_right会返回最右边（即最后一个相同价格元素的后一个位置）的索引，确保包括所有具有相同价格的物品。

题解中通过在accumulate函数使用initial=0参数考虑到了这种情况。如果所有的items价格都高于某个查询值，bisect_right将返回0，因为没有任何价格是小于或等于该查询价格的。因此，mx列表中索引0的值（由initial=0提供）将被返回，表示没有任何物品的价格低于该查询值，对应的最大美丽值为0。