【教3妹学编程-算法题】找到 Alice 和 Bob 可以相遇的建筑

发布时间:2023年12月17日

插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。
坚持不懈,越努力越幸运,大家一起学习鸭~~~

瑟瑟发抖

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;
    }
}

文章来源:https://blog.csdn.net/kangbin825/article/details/135047492
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。