力扣218. 天际线问题


力扣218. 天际线问题解析

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度,请返回 由这些建筑物形成的 天际线

每个建筑物的几何信息由数组 buildings 表示,其中三元组 buildings[i] = [lefti, righti, heighti] 表示:

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形,在高度为 0 的绝对平坦的表面上。

天际线 应该表示为由 “关键点” 组成的列表,格式 [[x1,y1],[x2,y2],…] ,并按 x 坐标 进行 排序关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点,y 坐标始终为 0 ,仅用于标记天际线的终点。此外,任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意:输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案;三条高度为 5 的线应该在最终输出中合并为一个:[…[2 3], [4 5], [12 7], …]

示例 1:

输入:buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出:[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释:
图 A 显示输入的所有建筑物的位置和高度,
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。

示例 2:

输入:buildings = [[0,2,3],[2,5,3]]
输出:[[0,3],[5,0]]

提示:

1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings 按 lefti 非递减排序

解析:

这个题目的要求很明确,输入的是每个建筑物在坐标中的x和y的坐标,要求我们输出关键点,显而易见的关键点就是高层建筑的左上角部分,但是由于建筑物的阴影遮罩问题,关键点是位于相对于高层建筑物的底层建筑物的相对投影处,我们需要建立一个算法来进行这个问题的求解。

找到一个非常不错的题解视频,引用了一下这个ppt:https://www.bilibili.com/video/BV1yq4y1J73s?from=search&seid=18167085271206266066&spm_id_from=333.337.0.0

我们这里用到的是这里用到的是所谓的扫描线用法,因为每一个建筑物有两条边平行与y轴,我们可以设置建筑物的将建筑物的左顶点坐标的y取负值,(输入给了每个建筑物的具体坐标,那我们就可以通过这一特点进行这一技巧的使用),我们需要新建立一个堆,具体用法结合图片所示:

我们直接来看下面的1~10,规则就是遇到负数就把其换算成正数入堆,同时这个正数和堆中的其他正数进行比较大小,如果这个数字是最大的,就把x轴的坐标和该正数一起返回,如果不是最大的,进行下一个坐标的入堆/出堆,如果遇到了正数(即某一建筑物的右侧边缘),我们就需要对其在堆中的数据进行出堆,如果出堆的这个数字并不是堆中最大的数字,那么这个地方不是关键点,进行下一个坐标的入堆/出堆,如果是最大的,那么就把x轴的坐标和该正数一起返回

简单总结边缘线算法那就是

从左自右扫描每一条边缘线,遇到左比阿奴原先koi入堆建筑物高度,遇到右边缘线就出堆建筑物高度

若堆内高度发生了变化,则表明遇到了天际线的关键点

关键点表示为当前边缘线的x的坐标和堆内最大值,即[x,queue.top()]

但是在代码实现逻辑上我们还需要注意一种情况

现在紫色建筑物和绿色建筑物投影链接在一起,我们入堆的时候就需要由低到高入堆,不然扫描到绿色建筑物就会弹出,导致x,0成为关键点

具体实现如下:

我使用的是大顶堆,并设置了第一个堆内元素,这样就能扫到第一个关键点,然后就行扫描比对删除就可以了,但是我们弹出堆的时候只能弹出对应的数值,而不是大顶堆只能弹出最大的那个数

代码:

class Solution {

public List<List<Integer>> getSkyline(int[][] buildings) {

List<List<Integer>> points = new ArrayList<>();

//求出左上角和右上角坐标, 左上角坐标的 y 存负数

for (int[] b : buildings) {

points.add(Arrays.asList(b[0], -b[2]));

points.add(Arrays.asList(b[1], b[2]));

}

//将所有坐标排序

points.sort(

(O1, O2) -> {

int x1 = O1.get(0), y1 = O1.get(1);

int x2 = O2.get(0), y2 = O2.get(1);

//这个就是对特殊情况的处理,由小变大

if (x1 != x2) return x1 - x2;

else return y1 - y2;

});

//默认的优先队列是小顶堆,我们需要大顶堆(算是吧),每次需要得到队列中最大的元素

Queue<Integer> queue = new PriorityQueue<>((O1, O2) -> O2 - O1);

queue.offer(0);

int preMax = 0;

List<List<Integer>> res = new ArrayList<>();

for (List<Integer> p : points) {

int x = p.get(0), y = p.get(1);

//左上角坐标

if (y < 0) queue.offer(-y);

//右上角坐标

else queue.remove(y);

int curMax = queue.peek();

//最大值更新了, 将当前结果加入

if (curMax != preMax) {

res.add(Arrays.asList(x, curMax));

preMax = curMax;

}

}

return res;

}

}

截图: