131. Building Outline

画建筑轮廓

LintCode链接

题目描述

水平面上有 N 座大楼,每座大楼都是矩阵的形状,可以用一个三元组表示 (start, end, height),分别代表其在x轴上的起点,终点和高度。大楼之间从远处看可能会重叠,求出 N 座大楼的外轮廓线。
外轮廓线的表示方法为若干三元组,每个三元组包含三个数字 (start, end, height),代表这段轮廓的起始位置,终止位置和高度。
参考下面的图,黑色线为建筑,红色线即为建筑的轮廓线

样例

1
2
3
4
5
6
对于下面三个链表,输出-1->2->4->null
[
2->4->null,
null,
-1->null
],

思路

  1. 首先肯定能想到的是需要对输入的所有数据进行排序,排序规则应该也很好想:
    • 如果start相等,height相等,则end大的在前面
    • 如果start相等,则height大的在前面
    • start小的在前面
  2. 考虑到以下两种情况
    • [1,5,3],[2,3,5],这种情况下,需要输出[1,2,3], [2,3,5], [3,5,3]
    • [1,5,5],[2,6,3], 这种情况下,需要输出[1.5,5], [5,6,3]
  3. 考虑情景2中的两种情况,我们需要在比较过程中把建筑灵活的进行拆分,然后重新加入到待比较的数组中,再进行排序,每次排序肯定不现实,所以用到了最大最小堆来减少排序带来的消耗

代码

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
class Solution {
public:
/*
* @param buildings: A list of lists of integers
* @return: Find the outline of those buildings
*/
vector<vector<int>> buildingOutline(vector<vector<int>> &buildings) {
// write your code here

vector<vector<int>> ret;

if (buildings.empty())
{
return ret;
}

auto func = [](vector<int> &left, vector<int> &right) {
if (left[0] == right[0] && left[2] == right[2])
{
return left[1] < right[1];
}

if (left[0] == right[0])
{
return left[2] < right[2];
}

return left[0] > right[0];
};
// 建堆;
make_heap(buildings.begin(), buildings.end(), func);

pop_heap(buildings.begin(), buildings.end(), func);
vector<int> cur_outline = *buildings.rbegin();
buildings.pop_back();

while (buildings.empty() == false)
{
pop_heap(buildings.begin(), buildings.end(), func);
vector<int> building = *buildings.rbegin();
buildings.pop_back();

if (building[0] > cur_outline[1])
{
// 建筑与当前轮廓分离;
ret.push_back(cur_outline);
cur_outline = building;
}
else if (building[2] > cur_outline[2])
{
// 建筑与当前轮廓未分离,并且高度比当前高;
if (building[1] < cur_outline[1])
{
// 该建筑没有当前轮廓宽,生成新的建筑;
vector<int> new_building = { building[1], cur_outline[1], cur_outline[2] };
buildings.push_back(new_building);
push_heap(buildings.begin(), buildings.end(), func);
}

cur_outline[1] = building[0];
ret.push_back(cur_outline);
cur_outline = building;
}
else if (building[2] == cur_outline[2])
{
// 建筑与当前轮廓未分离,并且高度相等,则看是否合并轮廓;
cur_outline[1] = max(cur_outline[1], building[1]);
}
else if (building[2] < cur_outline[2])
{
// 建筑与当前轮廓未分离,并且高度比当前小;
if (building[0] == cur_outline[1])
{
// 正好在边缘;
ret.push_back(cur_outline);
cur_outline = building;
}
else if (building[1] > cur_outline[1])
{
// 有重叠,并且该建筑比当前轮廓宽,生成新的建筑;
vector<int> new_building = { cur_outline[1], building[1], building[2] };
buildings.push_back(new_building);
push_heap(buildings.begin(), buildings.end(), func);
}
}
}

ret.push_back(cur_outline);
return ret;
}
};

附上我的测试代码

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
void printfOutline(vector<vector<int>> &outline)
{
cout << "[" << endl;
for (auto &i : outline)
{
cout << "\t[";
for (auto j : i)
{
cout << j << ",";
}
cout << "]" << endl;
}
cout << "]" << endl;
}

int main()
{
Solution s;
{
vector<vector<int>> input = { {1, 3, 3}, { 2, 4, 4 }, { 5, 6, 1} };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,3,3}
vector<vector<int>> input = { { 1, 3, 3 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,3,5}
vector<vector<int>> input = { { 1, 3, 3 }, {1,3,5} };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,3,5}, {3,4,3}
vector<vector<int>> input = { { 1, 4, 3 },{ 1,3,5 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,2,3}, {2,3,5}, {3,4,3}
vector<vector<int>> input = { { 1, 4, 3 },{ 2,3,5 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,5,5}
vector<vector<int>> input = { { 1, 4, 5 },{ 4,5,5 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,4,5}
vector<vector<int>> input = { { 1, 4, 5 },{ 2,3,3 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,2,3},{2,5,5}
vector<vector<int>> input = { { 1, 4, 3 },{ 2,5,5 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,5,3}
vector<vector<int>> input = { { 1, 4, 3 },{ 2,5,3 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,4,5},{4,5,3}
vector<vector<int>> input = { { 1, 4, 5 },{ 2,5,3 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,4,3}
vector<vector<int>> input = { { 1, 4, 3 },{ 1,3,3 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

{
// {1,4,3}
vector<vector<int>> input = { { 1, 4, 3 },{ 1,4,3 } };
vector<vector<int>> out = s.buildingOutline(input);
printfOutline(out);
}

while (1);
}