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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| // @Title: 天际线问题 (The Skyline Problem)
// @Author: 15816537946@163.com
// @Date: 2019-09-24 23:38:46
// @Runtime: 68 ms
// @Memory: 38.8 MB
/*
* @lc app=leetcode.cn id=218 lang=golang
*
* [218] 天际线问题
*
* https://leetcode-cn.com/problems/the-skyline-problem/description/
*
* algorithms
* Hard (39.01%)
* Likes: 57
* Dislikes: 0
* Total Accepted: 2.1K
* Total Submissions: 5.4K
* Testcase Example: '[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]'
*
*
* 城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图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], ...]
*
*
*/
type critical [][]int
func (h critical) Len() int {return len(h)}
func (h critical) Swap(i, j int) { h[i], h[j] = h[j], h[i]}
func (h critical) Less(i, j int) bool {
if h[i][0] == h[j][0] {
return h[i][1] < h[j][1]
}
return h[i][0] < h[j][0]
}
type hHeap []int
func (h hHeap) Len() int { return len(h)}
func (h hHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i]}
func (h hHeap) Less(i, j int) bool { return h[i] > h[j]} // contianer/heap实现了一个小顶堆，这里实现一个大顶堆
func (h *hHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *hHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func getSkyline(buildings [][]int) [][]int {
res := [][]int{}
var h = critical{}
for _, b := range buildings {
h = append(h, []int{b[0], -b[2]})
h = append(h, []int{b[1],b[2]})
}
sort.Sort(h)
prev := 0
pq := &hHeap{}
heap.Init(pq)
for _, v := range h {
if v[1] < 0 {
heap.Push(pq, -v[1])
} else {
index := 0
for (*pq)[index] != v[1] {
index++
}
heap.Remove(pq, index)
}
cur := 0
if len(*pq) > 0 {
cur = (*pq)[0]
}
if prev != cur {
res = append(res, []int{v[0], cur})
prev = cur
}
}
return res
}
|