https://leetcode.com/problems/most-beautiful-item-for-each-query
2070. Most Beautiful Item for Each Query
给一个 2D 整数数组 items 其中 items[i] = [price_i, beauty_i]
还有一个 0 索引的整数数组 queries
对于每个 query 找到价格小于或等于 query 当中的最大 beauty
如果找不到则为 0
照 queries 顺序回传 answer
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]
思路：
先排序
把 items 内的 beauty 逐项更新成前 n 项内的最大值
再用 bisect_right 搜寻
Python Code:
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) ->
List[int]:
items.sort()
for i in range(1, len(items)):
items[i][1] = max(items[i][1], items[i-1][1])
prices = [_[0] for _ in items]
answer = []
for query in queries:
idx = bisect_right(prices, query) - 1
answer.append(items[idx][1] if idx >= 0 else 0)
return answer
早上一眼感觉又是 bisect 就跑去研究了一下 其实之前好像有用过 不过忘了