Re: [閒聊] 每日leetcode

[dont (dont)]

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