2940.找到Alice和Bob可以相遇的建筑

链接：2940.找到Alice和Bob可以相遇的建筑
难度：Hard
标签：栈、树状数组、线段树、数组、二分查找、单调栈、堆（优先队列）
简介：请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。

题解 1 - python

• 编辑时间：2024-08-10
• 执行用时：324ms
• 内存消耗：39.23MB
• 编程语言：python
• 解法介绍：离线处理queries，过滤能立即得出答案的，剩余的一定是h[i] > h[j]，此时从左往右遍历h，维护当前下标之前的所有需求最小堆。

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        res = [-1 for _ in range(len(queries))]
        arr = [[] for _ in range(len(heights))]
        for idx, (i, j) in enumerate(queries):
            if i > j: i, j = j, i
            if i == j or heights[i] < heights[j]: res[idx] = j
            else: arr[j].append((heights[i], idx))
        q = []
        for cur_idx, h in enumerate(heights):
            while q and q[0][0] < h:
                idx = heappop(q)[1]
                res[idx] = cur_idx
            for v in arr[cur_idx]:
                heappush(q, v)
        return res