瑟瑟发抖

3妹：好冷啊， 冻得瑟瑟发抖啦
2哥 : 又一波寒潮来袭， 外面风吹的呼呼的。
3妹：今年的寒潮来的比去年要晚一些，但是该来的还是来了。
2哥 : 说的这么文艺，3妹还是个文艺青年啊。
3妹：2哥是什么青年，哦，忘了你是2哥，当然是2*青年啦，哈哈
2哥：3妹！！！
3妹：好啦好啦，2哥我错了。不跟你扯了，我要开始学习了~

吃瓜

题目：

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

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

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

请你能返回一个数组 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^4
1 <= heights[i] <= 10^9
1 <= queries.length <= 5 * 10^4
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length - 1

思路：

思考

离线做法+最小堆,

• 离线：按照自己定义的某种顺序回答询问（而不是按照输入顺序一个个地回答）。

不妨设 ai≤bi。

如果 ai=bi或者 heights[ai]<heights[bi]，那么 Alice 可以直接跳到 Bob 的位置，即 ans[i]=bi。

否则，我们可以在 bi处记录「左边有个 ai，它属于第 i 个询问」。

然后遍历 heights，同时用一个最小堆维护上面说的「记录」：遍历到 heights[i]时，把在下标 i 处的「记录」全部加到最小堆中。

在加到最小堆之前，我们可以回答左边所有高度小于 heights[i]的「记录」，其答案就是 i。

java代码：

class Solution {
    public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int[] ans = new int[queries.length];
        Arrays.fill(ans, -1);
        List<int[]>[] left = new ArrayList[heights.length];
        Arrays.setAll(left, e -> new ArrayList<>());
        for (int qi = 0; qi < queries.length; qi++) {
            int i = queries[qi][0], j = queries[qi][1];
            if (i > j) {
                int temp = i;
                i = j;
                j = temp; // 保证 i <= j
            }
            if (i == j || heights[i] < heights[j]) {
                ans[qi] = j; // i 直接跳到 j
            } else {
                left[j].add(new int[]{heights[i], qi}); // 离线
            }
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < heights.length; i++) { // 从小到大枚举下标 i
            while (!pq.isEmpty() && pq.peek()[0] < heights[i]) {
                ans[pq.poll()[1]] = i; // 可以跳到 i（此时 i 是最小的）
            }
            for (int[] p : left[i]) {
                pq.offer(p); // 后面再回答
            }
        }
        return ans;
    }
}