Re: [閒聊] 每日leetcode
2940. Find Building Where Alice and Bob Can Meet
## 思路
如果 a_i == b_i, 直接在b_i棟相遇
固定 a_i < b_i
如果b的高度比a高, 會在b的建築相遇
不然就是要在b之後 找第一棟高於heights[a_i]的建築
先掃Query記錄所有要找的 {b_i: (heights[a_i], query_idx)}
再掃builing
用min heap 存 (heights[a_i], query_idx)
如果當下的高度比前面的高, 就更新query_idx的答案
## Code
```python
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries:
List[List[int]]) -> List[int]:
n = len(heights)
res = [-1] * len(queries)
todo = defaultdict(list)
for idx, (alice, bob) in enumerate(queries):
if alice > bob:
alice, bob = bob, alice
if alice == bob or heights[alice] < heights[bob]:
res[idx] = bob
continue
todo[bob].append((heights[alice], idx))
heap = []
for i in range(n):
while heap and heap[0][0] < heights[i]:
_, idx = heapq.heappop(heap)
res[idx] = i
for max_height, idx in todo[i]:
heapq.heappush(heap, (max_height, idx))
return res
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.152 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734851373.A.7EE.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1216 之 1554 篇)：