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 就跑去研究了一下 其實之前好像有用過 不過忘了