【Leetcode Daily】2070每一个查询的最大美丽值

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二位整数数组来代表一个商品的价格和美丽值，然后根据一系列价格，查询不高于该数值能得到的最大美丽值。

思路分享

• 二分的基本思路可看【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置。

• 本题有好几个思路，下面的参考题解选取采用预处理 item 和 二分 的方法。

  https://leetcode.cn/problems/most-beautiful-item-for-each-query/solutions/1100468/jiang-xun-wen-chi-xian-pai-xu-by-endless-o5j0/

• 重点是预处理，将商品们按价格升序排列后，再只保留相同价格中的最大美丽值，这样就方便了后续的二分，同时也减少了复杂性。

• 至于二分，需要牢记的是二分取左右的含义，本题二分的是目标值加一的取右，所以如果这个值取到了 0，说明目标不存在，也就是不符合条件了。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort(key= lambda items : items[0])

        k = 0
        for i in range(1, len(items)):
            if items[i][1] > items[k][1]:
                k += 1
                items[k] = items[i]
        
        for i, x in enumerate(queries):
            j = bisect_right(items, x, 0, k+1, key=lambda items:items[0])
            queries[i] = items[j-1][1] if j else 0

        return queries