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

难度: Hard

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [a_i, b_i] 。第 i 个查询中，Alice 在建筑 a_i ，Bob 在建筑 b_i。

请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。

示例 1：

输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

示例 2：

输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出：[7,6,-1,4,6]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

提示：

1 <= heights.length <= 5 * 10⁴
1 <= heights[i] <= 10⁹
1 <= queries.length <= 5 * 10⁴
queries[i] = [a_i, b_i]
0 <= a_i, b_i <= heights.length - 1

Submission

运行时间: 219 ms

内存: 38.1 MB

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        n = len(heights)
        left = [[] for u in range(n)]
        ans = [-1] * len(queries)
        for i in range(len(queries)):
            a,b = queries[i]
            if a > b:
                a,b = b,a
            if a == b or heights[a] < heights[b]:
                ans[i] = b
            else:
                left[b].append((heights[a], i))

        pq = []
        for i in range(n):
            while pq and pq[0][0] < heights[i]:
                ans[heappop(pq)[1]] = i
            for item in left[i]:
                heappush(pq, item)
        return ans

Explain

这个题解使用了一个堆和一个数组来存储建筑信息。对于每个查询，首先检查 Alice 和 Bob 是否已经在同一个建筑中或者 Alice 可以直接移动到 Bob 的建筑，如果是，直接将答案设置为 Bob 的位置。否则，将 Alice 的位置和查询索引以元组形式添加到 Bob 所在建筑的列表中。然后，遍历所有建筑，对于每个建筑，将其左侧所有建筑的元组添加到堆中，并弹出堆中所有高度小于当前建筑高度的元组，将对应的答案设置为当前建筑的索引。这样，当处理完所有建筑后，就可以得到所有查询的答案。

时间复杂度: O(q + n log n)

空间复杂度: O(n)

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        n = len(heights)
        left = [[] for u in range(n)]  # 存储每个建筑左侧的建筑信息
        ans = [-1] * len(queries)
        for i in range(len(queries)):
            a,b = queries[i]
            if a > b:
                a,b = b,a
            if a == b or heights[a] < heights[b]:
                ans[i] = b
            else:
                left[b].append((heights[a], i))

        pq = []  # 堆
        for i in range(n):
            while pq and pq[0][0] < heights[i]:
                ans[heappop(pq)[1]] = i
            for item in left[i]:
                heappush(pq, item)
        return ans

Explore

此判断是为了处理最简单和直接的情况，以提高效率。如果Alice和Bob已经在同一个建筑中，那么Alice无需移动即可与Bob相遇。如果Alice可以直接移动到Bob的建筑，这意味着Alice位于Bob的左边且Alice的建筑不高于Bob的建筑，因此Alice可以直接移动到Bob的位置。这样直接判断可以减少不必要的计算，直接给出结果。

在此题解中，堆用于维护一个动态的，能够随时插入和删除元素的有序集合。堆确保了每次可以快速地获取并移除当前最小元素（这里是最低的建筑高度），这对于处理每个建筑时，检查并更新那些高度小于当前建筑高度的查询非常有用。使用堆而不是队列或栈的原因是，堆能够更高效地支持这种“动态的最值查询”操作，而普通的队列和栈不支持快速随机访问和中间元素的快速删除，这对于本问题中的需求来说是不够的。

操作中描述的`将其左侧所有建筑的元组添加到堆中`实际上指的是将当前建筑左侧相关的查询添加到堆中，而不是建筑本身。每个查询只因关联的Bob的位置一次性添加到堆中。因此，不会有重复的建筑信息加入到堆中。这种方式确保了堆中每个元素都是独立的查询，不会因重复的建筑信息而影响性能。

在题解中，每次处理一个新的建筑时，堆中会移除所有高度小于该建筑高度的元组，并将对应的查询答案设置为当前建筑的索引。这个操作确保一旦一个查询被处理（即被设置了答案），它就不会再次出现在堆中。堆中只存储还未找到有效答案的查询。这样通过逐步移除满足条件的最小元素，可以确保每个查询只被处理一次，避免了错误更新。