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

Binary search, https://leetcode.cn/problems/most-beautiful-item-for-each-query/

给你一个二维整数数组 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

python

import bisect
from typing import List


class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        # 首先按照价格升序排序，如果价格相同，则按美丽值降序排序
        items.sort(key=lambda x: (x[0], -x[1]))

        # 提取价格列表
        prices = [item[0] for item in items]

        # 处理items，使得每一个元素变为(price, max_beauty_until_now)
        max_beauty = 0
        for item in items:
            max_beauty = max(max_beauty, item[1])
            item[1] = max_beauty

        # 对每个查询进行处理
        n = len(queries)
        ans = [0] * n
        for i in range(n):
            pos = bisect.bisect_right(prices, queries[i]) - 1  # 找到小于等于查询价格的最大位置
            if pos >= 0:
                ans[i] = items[pos][1]
            else:
                ans[i] = 0  # 如果没有符合条件的物品，默认美丽值为0

        return ans


if __name__ == '__main__':
    sol = Solution()
    print(sol.maximumBeauty([[10, 1000]], [5]))  # 示例输出应为[0]，因为没有物品的价格小于等于5
    # 另一个测试用例
    print(sol.maximumBeauty([[1, 2], [3, 2], [2, 4], [5, 6], [3, 5]], [1, 2, 3, 4, 5, 6]))  # 应输出[2, 4, 5, 5, 6, 6]

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

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