Re: [閒聊] 每日leetcode
看板Marginalman作者JerryChungYC (JerryChung)時間1年前 (2024/11/12 19:33)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1116/1548 (看更多)
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 就跑去研究了一下 其實之前好像有用過 不過忘了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.80.152 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731411237.A.DD0.html
推
11/12 19:38,
1年前
, 1F
11/12 19:38, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1116 之 1548 篇)：