题目大意：
天际线问题
城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。
每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标，Hi 是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri – Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。
例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。
输出是以 [ [x1,y1], [x2, y2], [x3, y3], … ] 格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。
说明:
- 任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。
- 输入列表已经按左 x 坐标 Li 进行升序排列。
- 输出列表必须按 x 位排序。
- 输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=218
解题思路分析：
本题是Leetcode中相对较难的一道Hard题目，另外在lintcode中本题的级别被定义为Super。不过，难题不代表没有解决办法，只要缕清题目的命脉，思路还是很容易想出来的。
首先明确一点，题目中提到的关键点，一定是在建筑物的左右边缘上，从例子的轮廓图中可以发现，所有关键点都发生在高度发生变化的坐标位，这些坐标位或是某个建筑物的左边，或是某个建筑物的右边，因此，我们可以先统计出所有建筑物的纵边: [建筑物1左边，建筑物1右边，建筑物2左边，建筑物2右边 … 建筑物n左边，建筑物n右边]。我们可以使用一个数组代表一个边，arr[0]为该边x坐标，arr[1]为该边高度。最终的结果一定是在这些边中产生，接下来需要考虑哪些边是非关键边，剔除掉这些即是结果。
我们看下关键边的特点是什么，对于左边，如果当前边的高度大于其他同x坐标上的所有建筑物高度，那么它就是一个关键点，该关键点坐标为当前边的x坐标以及高度坐标。对于右边，如果它的高度大于其他所有同x坐标上的建筑物，它则是一个关键点，该点的x坐标为其本身，注意纵坐标并非是其高度，而是除了其自身之外的最高建筑物的高度（如果没有其它建筑物时，y坐标为0）。
以上就是基本的思路，解题时还需要一些细节方面的处理，因此我们来总结一下解题过程：
- 首先利用题目给出的buildings数组，统计出所有建筑物的纵边。上文说过，我们利用数组来记录每条边的信息，arr[0]为该边x坐标，arr[1]为该边高度，这里为了区分左边和右边，我们可以将右边的高度设置为负数。然后我们需要对这些边进行排序，排序时，优先x坐标升序排列，当两条边的x坐标相同时，高度大的排列在前。这样做的目的是避免高度较小的边先于高度较大的边出现时，误将高度较小的判断为关键点。
- 按顺序循环每个边，如果是左边（高度大于0），查看其是否是最高的，如果是将其加入返回结果。反之其不是关键边。同时将其高度加入到保存当前所有高度的列表heights中。
- 如果是右边（高度小于0），首先看其高度的绝对值是否是当前最高的边，同时注意一点，他不仅需要是最高边，同时还要保证他要高于第二高的边才可以，否则他不能成为关键点。满足条件的话，将其坐标加入到返回结果，此时的x坐标为当前边的x，y坐标应为第二高的边的高度（如果不存在其他边是，y为0）。最后还不要忘记将其从高度列表heights中删除。
实现代码：
public List<List<Integer>> getSkyline(int[][] buildings) {
List<int[]> list = new ArrayList<>(); // 统计建筑物的所有纵边
for(int build[] : buildings){
// 左边
list.add(new int[]{build[0],build[2]});
// 右边（便于区分，高度设为负数）
list.add(new int[]{build[1],-build[2]});
}
// 排序边
Collections.sort(list, (x1,x2)->x1[0]-x2[0]==0?x2[1]-x1[1]:x1[0]-x2[0]);
List<List<Integer>> res = new ArrayList<>(); // 返回结果
List<Integer> heights = new ArrayList<>(); // 当前高度列表
int maxHeight=0; // 当前最大高度
for(int[] b : list){ // 循环每一条边
if(b[1]>0){ // 左边
if(b[1]>maxHeight){ // 是最高边
// 加入返回结果
List<Integer> l = new ArrayList<>();
l.add(b[0]);
l.add(b[1]);
res.add(l);
// 更新最高边
maxHeight=b[1];
}
// 当前边高度加入高度列表
heights.add(b[1]);
}else{ // 右边
int h=-b[1]; // 右边高度
if(h==maxHeight){ // 右边为当前最高边
// 降序排序高度列表
Collections.sort(heights, (x1,x2)->x2-x1);
// 第二高的边
int secHeight=heights.size()>1?heights.get(1):0;
// 当前右边大于第二高的边
if(h>secHeight){
// 加入返回结果
List<Integer> l = new ArrayList<>();
l.add(b[0]);
l.add(secHeight);
res.add(l);
// 右边代表此建筑物结束位置，更新最高边为第二高的边
maxHeight=secHeight;
}
}
// 从高度列表删除此建筑物的左边
heights.remove(Integer.valueOf(h));
}
}
return res;
}本题解法执行时间为129ms。
Runtime: 129 ms, faster than 44.41% of Java online submissions for The Skyline Problem.
Memory Usage: 49 MB, less than 27.59% of Java online submissions for The Skyline Problem.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-218-the-skyline-problem-解题思路分析/