2940. 找到 Alice 和 Bob 可以相遇的建筑 (opens new window)

1.单调栈+跳表查询

思路：使用单调栈维护每个元素右侧第一个比它的元素的索引，并将结果保存到数组。查询时，需要遍历数组找到同时满足比heights[queries[0]]和heights[queries[1]]都大的索引位置，遍历过程类似于跳表。

极端条件下100001，1，2，3，4，5，6 . . . 100000，时间复杂度达到O(nq)，结果用例似乎没卡。可以使用二分查找，进一步优化遍历rightMaximum数组，时间复杂度为O(log(n)q)。

查询时对于两人的位置min，max存在两种情况：

• heights[min]小于heights[max]：那么min可以直接跳到max位置，查询结束。
• heights[min]大于等于heights[max]：则需要根据max依次搜索“最大右侧索引数组”，对于每次max可跳跃的位置midInx，当且仅当heights[midInx]也满足大于heights[min]，两个人才可同时移动到该位置。

class Solution {
    public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int[] rightMaximum = new int[heights.length];
        Stack<int[]> stack = new Stack<>();
        Arrays.fill(rightMaximum,-1);
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] > stack.peek()[0]) {
                int[] pop = stack.pop();
                rightMaximum[pop[1]] = i;
            }
            stack.push(new int[]{heights[i], i});
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int min = Math.min(queries[i][0], queries[i][1]);
            int max = Math.max(queries[i][0], queries[i][1]);
            if(min==max||heights[min]<heights[max]) res[i] = max;
            else{
                 int midInx = rightMaximum[max];
                while (midInx!=-1) {
                    int mid = heights[midInx];
                    if (mid > heights[min]) {
                        res[i] = midInx;
                        break;
                    }
                    midInx = rightMaximum[midInx];
                }
                if(midInx==-1) res[i]=-1;
            }
        }
        return res;
    }
}

2.离线+最小堆

离线：按照自己定义的某种顺序，来进行回答询问。而不按照输入的查询顺序。

离线预处理：对于每个查询(a,b)，假设a<b，保存每个以索引b为右端点的所有查询对。即Map<Integer，List<int[]>>，其中每个查询对保存左端点的高度heights[b]，以及查询索引。

定义优先级队列(最小堆)按照左查询端点高度升序排序的最小堆。

遍历heights数组，对于第i个位置元素：

• 将最小堆顶元素高度小于heights[i]的查询对依次出队，查询结果即为i。
• 以第i个位置为查询右端点的所有查询对入对。

大小顺序如何保证？

• 根据最小堆，可以保证出队时，一定有heights[i]大于左端点元素高度heights[a]
• 预处理构造查询对时，保证左端点元素heights[a]一定大于等于右端点元素heights[b]
• 因此位置 i 一定是两个人可以到达的位置。