大楼轮廓实现及优化

  |   分类   |   热度 ℃

前言

LintCode 是专注代码面试的在线评测系统，有很多代码题，可以用 Java、C++、Python 在线答题，我觉得还不错，就决定把做一做这些题，然后把题目的实现、优化思路写下来，一来是为了有更深的理解，二来是讨论一下还有没有更好的方法。

问题

LintCode：大楼轮廓 超难

描述

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

样例

给出三座大楼：

[
　[1, 3, 3],
　[2, 4, 4],
　[5, 6, 1]
]

外轮廓线为：

[
　[1, 2, 3],
　[2, 4, 4],
　[5, 6, 1]
]

实现

一开始看到这道题难度是超难我是不相信的，因为看起来很容易找到思路，然而测试用数据却非常大，很难不超时完成，这让我非常感兴趣，用了很久来做这道题，以下是我做这道题的思路，由于用语言描述过于复杂，所以采用动图的方式来描述绘制过程（手机浏览器可能会有些问题，建议用电脑看），拟定输入数据为：

[
　[7,9,5],
　[1,3,3],
　[2,5,4],
　[12,13,2],
　[4,10,2],
　[11,14,4]
]

无序逐个插入

问题分析

大楼的数组并不是有序的，所以首先想到了逐个插入，再根据包含、相交、被包含等不同的情况来绘制逐个绘制轮廓，如下图：

实现 - C++

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
class Solution {
public:
    vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
        vector<vector<int>> result;
        vector<int> buffer1;
        int size = buildings.size();
        for(int j = 0; j < size; j++){
            buffer1 = buildings[j];
            if(result.size() == 0){
                result.push_back(buffer1);
                continue;
            }
            if(result.back()[1] < buffer1[0]){
                result.push_back(buffer1);
                continue;
            }
            if(result.front()[0] > buffer1[1]){
                result.insert(result.begin(), buffer1);
                continue;
            }
            for(int i = 0; i < result.size(); i++){
                if(i > 0){
                    if(result[i -1][1] != result[i][0]){
                        vector<int> buffer2;
                        buffer2.push_back(result[i - 1][1]);
                        buffer2.push_back(result[i][0]);
                        buffer2.push_back(buffer1[2]);
                        result.insert(result.begin() + i, buffer2);
                        continue;
                    }
                }
                if(buffer1[2] > result[i][2]){
                    if(result[i][1] < buffer1[0]){
                        continue;
                    }
                    if(result[i][0] > buffer1[1]){
                        continue;
                    }
                    if(buffer1[0] <= result[i][0] 
                        && buffer1[1] >= result[i][1]){
                        result[i][2] = buffer1[2];
                    }else if(buffer1[0] > result[i][0] 
                        && buffer1[1] >= result[i][1]){
                        vector<int> buffer2;
                        buffer2.push_back(buffer1[0]);
                        buffer2.push_back(result[i][1]);
                        buffer2.push_back(buffer1[2]);
                        result[i][1] = buffer1[0];
                        result.insert(result.begin() + i + 1, buffer2);
                        i++;
                    }else if(buffer1[0] <= result[i][0] 
                        && buffer1[1] < result[i][1]){
                        vector<int> buffer2;
                        buffer2.push_back(result[i][0]);
                        buffer2.push_back(buffer1[1]);
                        buffer2.push_back(buffer1[2]);
                        result[i][0] = buffer1[1];
                        result.insert(result.begin() + i, buffer2);
                        break;
                    }else if(buffer1[0] > result[i][0] 
                        && buffer1[1] < result[i][1]){
                        vector<int> buffer2;
                        buffer2.push_back(result[i][0]);
                        buffer2.push_back(buffer1[0]);
                        buffer2.push_back(result[i][2]);
                        result[i][0] = buffer1[1];
                        result.insert(result.begin() + i, buffer1);
                        result.insert(result.begin() + i, buffer2);
                        break;
                    }
                }
            }
            if(result.back()[1] < buffer1[1]){
                vector<int> buffer2;
                buffer2.push_back(result.back()[1]);
                buffer2.push_back(buffer1[1]);
                buffer2.push_back(buffer1[2]);
                result.push_back(buffer2);
            }
            if(result.front()[0] > buffer1[0]){
                vector<int> buffer2;
                buffer2.push_back(buffer1[0]);
                buffer2.push_back(result.front()[0]);
                buffer2.push_back(buffer1[2]);
                result.insert(result.begin(), buffer2);
            }
        }
        for(int i = 0; i < result.size(); i++){
            if(result[i][0] == result[i][1]){
                result.erase(result.begin() + i);
                i--;
            }
            if(i != 0){
                if(result[i - 1][2] == result[i][2] 
                    && result[i - 1][1] == result[i][0]){
                    result[i][0] = result[i - 1][0];
                    result.erase(result.begin() + i - 1);
                    i--;
                }
            }
        }
        return result;
    }
};

结果分析

  • 结果：非常慢，代码实际写起来远比想象的要复杂，当新大楼与旧轮廓线相交时，需要分块儿遍历旧轮廓线，效率非常低，LintCode 测试数据跑到 $53\%$ 时就超时了。
  • 分析：当大楼无序插入时，需要考虑情况非常多，不仅代码复杂容易混乱且执行效率低下，所以也未进行进一步的改正便直接放弃。直接考虑排序后再进行逐个插入，以减少需要考虑的情况。

有序逐个插入

问题分析

由于考虑到无序插入时情况过多且遍历次数过多，导致时间复杂度很高，在数据量大时运行效率过低，所以便打算采用预排序来减少遇到的情况，具体过程如下图：

结果预测

由于思考这种方法时想到了更高效的方法，所以没有进行代码实现。虽然上图的逻辑看起来比较简单，但是当大量大楼重叠时，需要频繁的修改旧的轮廓，相对于第一种方法来说也只是减少了遍历的次数，但是并不能免于分段遍历旧轮廓，而且判断是否与旧轮廓相交、包括、被包括需要做的对比也比较多。可想而知，此方法也并不能通过测试。

无序逐个插入 - 拆分为单位大楼

问题分析

由于采用 (start, end, height) 三元组的形式存储数据，当无序插入时只能采用遍历判断的方式来分情况讨论，由此导致的逻辑混乱使复杂度很难降低。便想出了将 三元组（[1,4,3]） 转化为若干个连续的单位大楼([1,3],[2,3],[3,3])（因为每个单位大楼跨度都为一，所以 end 可以不需要表示了），这样存储时就可以将每栋楼的 start 作为下标。此时便只需要对比每个单位大楼的高度来决定是否修改轮廓，整体过程与第一种方法一致：

实现 - C++

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
class Solution {
public:
    vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
        vector<vector<int>> result;
        vector<int> draft;
        int dSize = 0;
        int bSize = buildings.size();
        for(int i = 0; i < bSize; i++){
            //新加大楼超出draft范围则需要扩容
            int cEnd = buildings[i][1];
            if(dSize < cEnd){
                while(dSize < cEnd){
                    draft.push_back(0);
                    dSize++;
                }
            }
            //更新大楼轮廓
            int cValue = buildings[i][2];
            for(int j = buildings[i][0] - 1; j < cEnd - 1; j++){
                if(draft[j] < cValue){
                    draft[j] = cValue;
                }
            }
        }
        //将单位大楼模式转为三元组格式
        int start = 0;
        int value = 0;
        for(int i = 0; i < dSize; i++){
            if(draft[i] != value){
                if(start < i && value != 0){
                    vector<int> building;
                    building.push_back(start + 1);
                    building.push_back(i + 1);
                    building.push_back(value);
                    result.push_back(building);
                }
                start = i;
                value = draft[i];
            }
        }
        return result;
    }
};

结果分析

  • 结果：成功将 LintCode 测试数据跑到了 $77\%$ 。
  • 分析：转化思路后，从代码量上来看，逻辑复杂程度大大降低，拆分大楼后坐标按 vector 坐标存储，提高了随机存取的效率，但是由于拆分存储，空间复杂度大大提高。尽管每一步都是简单的大小对比，数据量较大时仍然会消耗大量的时间，这应该也是不能通过 LintCode 测试的根本原因。

有序插入 - 拆分为左右墙

问题分析

这种方法解决问题的基本思想就是将每座大楼用 左右两面墙表示([1,3],[4,-3]) 替换 三元组表示([1,4,3])，左墙的高度为正，右墙的高度为负，也可以理解为高度的跳跃，因为是从左到右扫描，所以左墙高度升高，右墙高度降低。拆分为墙之后按坐标排序，如果坐标相同则根据高度反向排序，因为优先左墙可以避免同样高且位置相同的两面墙先结束再开始的情况，而且优先更高的墙也可以减少先低墙后高墙是否需要划轮廓的不必要判断。然后从左至右逐个墙面进行扫描，如下图：

实现 - C++

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
#include <set>
//墙的数据结构
struct JUMP  
{  
    int index; 
    int height;  
    JUMP(int a, int b) : index(a), height(b){}
    //操作符<的定义，用于排序
    bool operator< (const JUMP &j)  const  {
        if(index != j.index){
            return index < j.index;
        }else{
            //相等时由高到底排序
            return height > j.height;
        }
    }
}; 
class Solution {
public:
    vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
        //数量提前取出来，避免多次调用浪费时间
        int numOfBuilding = buildings.size();
        int sizeOfJumps = numOfBuilding * 2;
        //拆分为墙存储
        vector<JUMP> jumps;
        for(int i = 0; i < numOfBuilding; i++){
            jumps.push_back(JUMP(buildings[i][0], buildings[i][2]));
            jumps.push_back(JUMP(buildings[i][1], - buildings[i][2]));
        }
        //对墙进行排序
        sort(jumps.begin(), jumps.end());
        //绘制轮廓
        vector<vector<int>> result;
        //没有结束的大楼存起来，multiset插入时会自动排序
        multiset<int> current;
        int prevJump = 0;
        for(int i = 0; i < sizeOfJumps; i++){
            //没有没结束的大楼，添加左墙高度，设置线段起点
            if(current.empty()){
                current.insert(jumps[i].height);
                prevJump = jumps[i].index;
                continue;
            }
            //如果是左墙
            if(jumps[i].height > 0){
                //如果高于没结束的最高的大楼，且线段长度大于0
                if(jumps[i].height > *current.rbegin() 
                && prevJump < jumps[i].index){
                    //画线 设置为起点
                    vector<int> jump;
                    jump.push_back(prevJump);
                    jump.push_back(jumps[i].index);
                    jump.push_back(*(--current.end()));
                    result.push_back(jump);
                    prevJump = jumps[i].index;
                }
                //添加墙
                current.insert(jumps[i].height);
            }else{
                //右墙 而且是存起来最高的大楼并且只有一座 线段长度大于0
                if(jumps[i].height == -*current.rbegin() 
                && current.count(-jumps[i].height) < 2 
                && prevJump < jumps[i].index){
                    //画线 设置为起点
                    vector<int> jump;
                    jump.push_back(prevJump);
                    jump.push_back(jumps[i].index);
                    jump.push_back(*current.rbegin());
                    result.push_back(jump);
                    prevJump = jumps[i].index;
                }
                //大楼结束 删除存储的大楼
                current.erase(current.lower_bound(-jumps[i].height));
            }
        }
        return result;
    }
};

结果分析

  • 结果：经测试 C++ 最快可以 3326ms 通过 LintCode 测试。
  • 分析：由于判断的条件少，并且一次性绘制轮廓不进行修改，效率很高，经受住了大数据量的考验。

  • 细节：

    • 遍历前取出次数，避免重复执行影响遍历效率
    • 数据结构设计有缺陷，左右通过正负判断降低了代码的简洁程度
    • 这道题数据结构的选择很重要，要说的比较多，后面使用单独一节来说明。

数据结构的选择

最终作为选择的容器分别为 vector 和 multiset。

  • vector：由于 vector 属于顺序容器，内部由 数组 实现，随机存取效率高，尾部插入删除效率高，中间插入删除效率低。
  • multiset：与 set 唯一的不同就是可以添加等值元素，都属于关联容器，内部由 红黑树 实现，插入时会自动排序，检索效率高。

同样是排序，墙的排序由于不需要插入一次取一次，所以选择了 vector ，std::sort() 对 vector 的排序是优化过的快排，效率高于 红黑树 的堆排序。
最开始是存数组然后自己写快排排序，然后发现 std::sort() 的排序比手写的要快，所以采用了 vector 搭配 std::sort() 进行墙的存储排序。
相对于墙的存储，未结束墙存储使用的 multiset，由于每次插入后都要取一次最大值，multiset 的堆排序作为插入排序的一种，每次插入一个元素都是有序的，相对于快排的一次成型，更适合存储未结束墙的情况。
起先是打算用 数组存储 + 直接插排 的方式，简直是低估了这道题的难度，最终不得不选用 multiset。

总结

因为写两个语言的代码实在是太浪费时间，所以实现就只使用 C++ 了，主要还是看思路。
通过对这道题的执着，学到了不少的东西，最重要的是做题的心态，这里要感谢 @Cicy_Lee 在我不知道难度的情况提问我这道题，如果当时看到这道题难度是超难的话，可能都不会去感兴趣甚至打开，何况是做出来。所以遇到问题还是不要停留在思考一下的程度上，尽量去做一下，因为做起来可能远比想的复杂。
另外，描述很多东西总是免不了用动画来表示， 但是 After Effect 画动图效率忒低了，却又找不到很好的图形化 HTML5 动画模块的制作工具（是模块不是网页），如果谁有很好的工具，求推荐一个。如果实在没有的话，有人有兴趣一起开发一个的话请留言告诉我。
特别感谢一下 七牛云 提供的免费图床支持，个人认为国内最好用的图床，没有之一，也推荐给大家使用。


本文链接：大楼轮廓实现及优化
版权声明：本文章采用CC BY-NC-SA 3.0 CN许可协议进行许可。转载请注明出处！