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

You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.

If a person is in building i, they can move to any other building j if and only if i < j and heights[i] < heights[j].

You are also given another array queries where queries[i] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.

Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the ith query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.

 

Example 1:

Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
Output: [2,5,-1,5,2]
Explanation: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2]. 
In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5]. 
In the third query, Alice cannot meet Bob since Alice cannot move to any other building.
In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].
In the fifth query, Alice and Bob are already in the same building.  
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Example 2:

Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
Output: [7,6,-1,4,6]
Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7].
In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6].
In the third query, Alice cannot meet Bob since Bob cannot move to any other building.
In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4].
In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6].
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

 

Constraints:

• 1 <= heights.length <= 5 * 104
• 1 <= heights[i] <= 109
• 1 <= queries.length <= 5 * 104
• queries[i] = [ai, bi]
• 0 <= ai, bi <= heights.length - 1

/*
 * Problem: Given an array 'heights' representing the heights of buildings and an array 'queries' where each query contains two integers [a, b], 
 * we need to determine the leftmost building index where Alice starting at a and Bob starting at b can meet. 
 * Alice and Bob can only move to a building with a greater height than their current one. If no such building exists, return -1 for that query.
 */

import java.util.stream.IntStream;

public class Solution {
    public int[] canMeet(int[] heights, int[][] queries) {
        return IntStream.range(0, queries.length)
                .map(i -> findMeetingBuilding(heights, queries[i][0], queries[i][1]))
                .toArray();
    }

    private int findMeetingBuilding(int[] heights, int a, int b) {
        int n = heights.length;
        boolean[] reachableFromA = new boolean[n];
        boolean[] reachableFromB = new boolean[n];

        IntStream.range(a, n).takeWhile(i -> i == a || heights[i] > heights[a]).forEach(i -> reachableFromA[i] = true);
        IntStream.range(b, n).takeWhile(i -> i == b || heights[i] > heights[b]).forEach(i -> reachableFromB[i] = true);

        return IntStream.range(0, n).filter(i -> reachableFromA[i] && reachableFromB[i]).findFirst().orElse(-1);
    }
}

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

O(q + n log n)

O(n)