原文發(fā)表在我的博客：大樓輪廓實現(xiàn)及優(yōu)化
求關(guān)注、求交流、求意見缀雳、求建議。

問題

LintCode：大樓輪廓

描述

水平面上有 N 座大樓梢睛，每座大樓都是矩陣的形狀肥印，可以用三個數(shù)字表示 (start, end, height) ，分別代表其在 x 軸上的起點扬绪，終點和高度竖独。大樓之間從遠處看可能會重疊，求出 N 座大樓的外輪廓線挤牛。
外輪廓線的表示方法為若干三元組莹痢，每個三元組包含三個數(shù)字 (start, end, height) ，代表這段輪廓的起始位置墓赴，終止位置和高度竞膳。

樣例

給出三座大樓：

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

外輪廓線為：

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

實現(xiàn)

一開始看到這道題難度是超難我是不相信的，因為看起來很容易找到思路诫硕，然而測試用數(shù)據(jù)卻非常大坦辟，很難不超時完成，這讓我非常感興趣章办，用了很久來做這道題锉走，以下是我做這道題的思路滨彻，由于用語言描述過于復(fù)雜，所以采用動圖的方式來描述繪制過程（手機瀏覽器可能會有些問題挪蹭，建議用電腦看）亭饵，擬定輸入數(shù)據(jù)為：

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

無序逐個插入

問題分析

大樓的數(shù)組并不是有序的，所以首先想到了逐個插入梁厉，再根據(jù)包含辜羊、相交、被包含等不同的情況來繪制逐個繪制輪廓词顾，如下圖：

實現(xiàn) - C++

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;
    }
};

結(jié)果分析

• 結(jié)果：非常慢八秃，代碼實際寫起來遠比想象的要復(fù)雜，當新大樓與舊輪廓線相交時肉盹，需要分塊兒遍歷舊輪廓線昔驱，效率非常低，LintCode 測試數(shù)據(jù)跑到 53% 時就超時了上忍。
• 分析：當大樓無序插入時舍悯，需要考慮情況非常多，不僅代碼復(fù)雜容易混亂且執(zhí)行效率低下睡雇，所以也未進行進一步的改正便直接放棄。直接考慮排序后再進行逐個插入饮醇，以減少需要考慮的情況它抱。

有序逐個插入

問題分析

由于考慮到無序插入時情況過多且遍歷次數(shù)過多，導(dǎo)致時間復(fù)雜度很高朴艰，在數(shù)據(jù)量大時運行效率過低观蓄，所以便打算采用預(yù)排序來減少遇到的情況，具體過程如下圖：

結(jié)果預(yù)測

由于再思考這種方法時想到了更高效的方法祠墅，所以沒有進行代碼實現(xiàn)侮穿。雖然上圖的邏輯看起來比較簡單，但是當大量大樓重疊時毁嗦，需要頻繁的修改舊的輪廓亲茅，相對于第一種方法來說也只是減少了遍歷的次數(shù)，但是并不能免于分段遍歷舊輪廓狗准，而且判斷是否與舊輪廓相交克锣、包括、被包括需要做的對比也比較多腔长∠睿可想而知，此方法也并不能通過測試捞附。

無序逐個插入 - 拆分為單位大樓

問題分析

由于采用 (start, end, height) 三元組的形式存儲數(shù)據(jù)巾乳，當無序插入時只能采用遍歷判斷的方式來分情況討論您没，由此導(dǎo)致的邏輯混亂使復(fù)雜度很難降低。便想出了將 三元組（[1,4,3]） 轉(zhuǎn)化為若干個連續(xù)的單位大樓([1,3],[2,3],[3,3])（因為每個單位大樓跨度都為一胆绊，所以 end 可以不需要表示了）氨鹏，這樣存儲時就可以將每棟樓的 start 作為下標。此時便只需要對比每個單位大樓的高度來決定是否修改輪廓辑舷，整體過程與第一種方法一致：

實現(xiàn) - C++

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;
                }
            }
        }
        //將單位大樓模式轉(zhuǎn)為三元組格式
        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;
    }
};

結(jié)果分析

• 結(jié)果：成功將 LintCode 測試數(shù)據(jù)跑到了 77% 喻犁。
• 分析：轉(zhuǎn)化思路后，從代碼量上來看何缓，邏輯復(fù)雜程度大大降低肢础，拆分大樓后坐標按 vector 坐標存儲，提高了隨機存取的效率碌廓，但是由于拆分存儲传轰，空間復(fù)雜度大大提高。盡管每一步都是簡單的大小對比谷婆，數(shù)據(jù)量較大時仍然會消耗大量的時間慨蛙，這應(yīng)該也是不能通過 LintCode 測試的根本原因。

有序插入 - 拆分為左右墻

問題分析

這種方法解決問題的基本思想就是將每座大樓用 左右兩面墻表示([1,3],[4,-3]) 替換 三元組表示([1,4,3])纪挎，左墻的高度為正期贫，右墻的高度為負，也可以理解為高度的跳躍异袄，因為是從左到右掃描通砍，所以左墻高度升高，右墻高度降低烤蜕。拆分為墻之后按坐標排序封孙，如果坐標相同則根據(jù)高度反向排序，因為優(yōu)先左墻可以避免同樣高且位置相同的兩面墻先結(jié)束再開始的情況讽营，而且優(yōu)先更高的墻也可以減少先低墻后高墻是否需要劃輪廓的不必要判斷虎忌。然后從左至右逐個墻面進行掃描，如下圖：

實現(xiàn) - C++

#include <set>
//墻的數(shù)據(jù)結(jié)構(gòu)
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) {
        //數(shù)量提前取出來膜蠢，避免多次調(diào)用浪費時間
        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;
        //沒有結(jié)束的大樓存起來，multiset插入時會自動排序
        multiset<int> current;
        int prevJump = 0;
        for(int i = 0; i < sizeOfJumps; i++){
            //沒有沒結(jié)束的大樓莉兰，添加左墻高度狡蝶，設(shè)置線段起點
            if(current.empty()){
                current.insert(jumps[i].height);
                prevJump = jumps[i].index;
                continue;
            }
            //如果是左墻
            if(jumps[i].height > 0){
                //如果高于沒結(jié)束的最高的大樓，且線段長度大于0
                if(jumps[i].height > *current.rbegin() 
                && prevJump < jumps[i].index){
                    //畫線 設(shè)置為起點
                    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){
                    //畫線 設(shè)置為起點
                    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;
                }
                //大樓結(jié)束 刪除存儲的大樓
                current.erase(current.lower_bound(-jumps[i].height));
            }
        }
        return result;
    }
};

結(jié)果分析

• 結(jié)果：經(jīng)測試 C++ 最快可以 3326ms 通過 LintCode 測試贮勃。

• 分析：由于判斷的條件少贪惹，并且一次性繪制輪廓不進行修改，效率很高寂嘉，經(jīng)受住了大數(shù)據(jù)量的考驗奏瞬。

• 細節(jié)：

• 遍歷前取出次數(shù)枫绅，避免重復(fù)執(zhí)行影響遍歷效率

• 數(shù)據(jù)結(jié)構(gòu)設(shè)計有缺陷，左右通過正負判斷降低了代碼的簡潔程度

• 這道題數(shù)據(jù)結(jié)構(gòu)的選擇很重要硼端，要說的比較多并淋，后面使用單獨一節(jié)來說明。

數(shù)據(jù)結(jié)構(gòu)的選擇

最終作為選擇的容器分別為 vector 和 multiset珍昨。

• vector：由于 vector 屬于順序容器县耽，內(nèi)部由 數(shù)組 實現(xiàn)，隨機存取效率高镣典，尾部插入刪除效率高兔毙，中間插入刪除效率低。
• multiset：與 set 唯一的不同就是可以添加等值元素兄春，都屬于關(guān)聯(lián)容器澎剥，內(nèi)部由 紅黑樹 實現(xiàn)，插入時會自動排序赶舆，檢索效率高哑姚。

同樣是排序，墻的排序由于不需要插入一次取一次芜茵，所以選擇了 vector 叙量，std::sort() 對 vector 的排序是優(yōu)化過的快排，效率高于 紅黑樹 的堆排序九串。
最開始是存數(shù)組然后自己寫快排排序宛乃，然后發(fā)現(xiàn) std::sort() 的排序比手寫的要快，所以采用了 vector 搭配 std::sort() 進行墻的存儲排序蒸辆。
相對于墻的存儲，未結(jié)束墻存儲使用的 multiset析既，由于每次插入后都要取一次最大值躬贡，multiset 的堆排序作為插入排序的一種，每次插入一個元素都是有序的眼坏，相對于快排的一次成型拂玻，更適合存儲未結(jié)束墻的情況。
起先是打算用 數(shù)組存儲 + 直接插排 的方式宰译，簡直是低估了這道題的難度檐蚜，最終不得不選用 multiset。

總結(jié)

因為寫兩個語言的代碼實在是太浪費時間沿侈，所以實現(xiàn)就只使用 C++ 了闯第，主要還是看思路。
通過對這道題的執(zhí)著缀拭，學(xué)到了不少的東西咳短，最重要的是做題的心態(tài)填帽，這里要感謝 @Cicy_Lee 在我不知道難度的情況提問我這道題，如果當時看到這道題難度是超難的話咙好，可能都不會去感興趣甚至打開篡腌，何況是做出來。所以遇到問題還是不要停留在思考一下的程度上勾效，盡量去做一下嘹悼，因為做起來可能遠比想的復(fù)雜。
另外层宫，描述很多東西總是免不了用動畫來表示杨伙， 但是 After Effect 畫動圖效率忒低了，卻又找不到很好的圖形化 HTML5 動畫模塊的制作工具（是模塊不是網(wǎng)頁）卒密，如果誰有很好的工具缀台，求推薦一個。如果實在沒有的話哮奇，有人有興趣一起開發(fā)一個的話請留言告訴我膛腐。