题目内容
第一眼看到，“额，城市天际线（steam上一款游戏）？”，读了题目之后，明白它和游戏还真是有一点关系，那就是它真是城市的天际线。
所以这里的天际线的意思，其实是你在水平方向平视一个城市，它所展现出的轮廓，有点类似于工程制图里面的正视图。
那么建筑物在这道题中都以长方形来表示，与地面保持垂直，那么实际上，只需要给出房顶的坐标就可以确定一栋建筑。
题目要求就是求出这一条天际线，通过坐标点的形式来表示。
自己的解决思路
本着能自己做就先不看别人的思路的原则，至少浪费了五个小时以上的时间，我一直都没有编写出来，今天把之前的代码删了，重新整理了一遍思路，
还是写了出来。
自己的思路就很直白，维护当前的天际线，把剩下的建筑一栋一栋加进来就好，那么就涉及到很多情况的判断，这种思路最容易出错的地方就在：
- 一条线一定要以左端为准，这样在出现两栋刚好贴在一起的建筑的情况下，才不会出错。
- 将两条线的各种重叠情况判断清楚，分情况一一处理。这里情况有好几种，很容易遗漏或者绕晕。
- 初始情况的考虑，以及最后一条线的处理。
由于这样的想法很好想，但是写起来十分痛苦，写完之后调了好几遍才过，搞不好就写乱了，然后就调不出来。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| class Solution {
private int begin = 0;
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> roofs = new ArrayList<>();
int[] floor = {0, 0};
roofs.add(floor);
for ( int[] building : buildings ) {
helpAdd(roofs, building);
}
for ( int i = 0; i < roofs.size() - 1; i++ ) {
int[] roof = roofs.get(i);
int[] next = roofs.get(i+1);
if ( roof[1] == next[1] ) {
roofs.remove(i+1);
i--;
}
}
int[] first = roofs.get(0);
if ( first[1] == 0 ) {
roofs.remove(0);
}
return roofs;
}
private void helpAdd(List<int[]> roofs, int[] bu) {
for ( int i = begin; i < roofs.size() - 1; i++ ) {
int[] roof = roofs.get(i);
int[] next = roofs.get(i+1);
if ( roof[0] >= bu[1] ) {
break;
}
if ( roof[1] >= bu[2] || next[0] <= bu[0] ) {
continue;
}
if ( roof[0] < bu[0] ) {
if ( next[0] <= bu[1] ) {
int[] nroof = {bu[0], bu[2]};
roofs.add(++i, nroof);
begin = i;
} else {
int[] nroof = {bu[0], bu[2]};
int[] nroof2 = {bu[1], roof[1]};
roofs.add(i+1, nroof2);
roofs.add(i+1, nroof);
begin = i + 1;
break;
}
} else {
if ( next[0] <= bu[1] ) {
roof[1] = bu[2];
} else {
int[] nroof = {bu[1], roof[1]};
roof[1] = bu[2];
roofs.add(i+1, nroof);
break;
}
}
}
int[] last = roofs.get(roofs.size()-1);
if ( last[1] < bu[2] && last[0] < bu[1] ) {
if ( last[0] < bu[0] ) {
int[] nroof = {bu[0], bu[2]};
int[] nroof2 = {bu[1], last[1]};
roofs.add(nroof);
roofs.add(nroof2);
begin = roofs.size() - 2;
} else {
int[] nroof = {bu[1], last[1]};
last[1] = bu[2];
roofs.add(nroof);
}
}
}
}
|
算法复杂度：最坏情况$O(n^2)$，通常情况应该接近$O(n)$，主要是因为原本的建筑的左端起点已经排好序了，大量情况下只需要比较最后的几条线。
运行时间：4ms
击败：99.57%
另外，看了3ms的答案，别人的思路应该和我差不多，但是别人数据结构用了链表，这就是别人的优势了，也不知道为什么自己在写的时候没有想到。
广泛的解决思路
看了一下比较广泛的解决思路，主要使用了优先队列，其实就是一个对高度的排序，然后将一个一个点确定下来。不得不说这个思路很巧妙，
想要一下子想到这个思路，并不容易。但是一旦理清了这个思路，写起来又会相对简单一点。
参考资料：
leetCode上一哥们分享的解释，是真的强
YouTube上一个视频讲解，口音有点…