[LintCode]大樓輪廓實現(xiàn)及優(yōu)化

原文發(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ù)雜，當(dāng)新大樓與舊輪廓線相交時，需要分塊兒遍歷舊輪廓線，效率非常低，LintCode 測試數(shù)據(jù)跑到 53% 時就超時了。
  • 分析：當(dāng)大樓無序插入時，需要考慮情況非常多，不僅代碼復(fù)雜容易混亂且執(zhí)行效率低下，所以也未進行進一步的改正便直接放棄。直接考慮排序后再進行逐個插入，以減少需要考慮的情況。

有序逐個插入

問題分析

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

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

由于再思考這種方法時想到了更高效的方法，所以沒有進行代碼實現(xiàn)。雖然上圖的邏輯看起來比較簡單，但是當(dāng)大量大樓重疊時，需要頻繁的修改舊的輪廓，相對于第一種方法來說也只是減少了遍歷的次數(shù)，但是并不能免于分段遍歷舊輪廓，而且判斷是否與舊輪廓相交、包括、被包括需要做的對比也比較多?？上攵?，此方法也并不能通過測試。

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

問題分析

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

實現(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ù)雜程度大大降低，拆分大樓后坐標(biāo)按 vector 坐標(biāo)存儲，提高了隨機存取的效率，但是由于拆分存儲，空間復(fù)雜度大大提高。盡管每一步都是簡單的大小對比，數(shù)據(jù)量較大時仍然會消耗大量的時間，這應(yīng)該也是不能通過 LintCode 測試的根本原因。

有序插入 - 拆分為左右墻

問題分析

這種方法解決問題的基本思想就是將每座大樓用 左右兩面墻表示([1,3],[4,-3]) 替換 三元組表示([1,4,3])，左墻的高度為正，右墻的高度為負，也可以理解為高度的跳躍，因為是從左到右掃描，所以左墻高度升高，右墻高度降低。拆分為墻之后按坐標(biāo)排序，如果坐標(biāo)相同則根據(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 在我不知道難度的情況提問我這道題，如果當(dāng)時看到這道題難度是超難的話，可能都不會去感興趣甚至打開，何況是做出來。所以遇到問題還是不要停留在思考一下的程度上，盡量去做一下，因為做起來可能遠比想的復(fù)雜。
另外，描述很多東西總是免不了用動畫來表示， 但是 After Effect 畫動圖效率忒低了，卻又找不到很好的圖形化 HTML5 動畫模塊的制作工具（是模塊不是網(wǎng)頁），如果誰有很好的工具，求推薦一個。如果實在沒有的話，有人有興趣一起開發(fā)一個的話請留言告訴我。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 標(biāo)簽（空格分隔）： STL 運用STL，可以充分利用該庫的設(shè)計，讓我為簡單而直接的問題設(shè)計出簡單而直接的解決方案，...
    認真學(xué)計算機閱讀 1,600評論 0贊 10
  • 1. Java基礎(chǔ)部分 基礎(chǔ)部分的順序：基本語法，類相關(guān)的語法，內(nèi)部類的語法，繼承相關(guān)的語法，異常的語法，線程的語...
    子非魚_t_閱讀 34,823評論 18贊 399
  • 教你如何迅速秒殺掉：99%的海量數(shù)據(jù)處理面試題 本文經(jīng)過大量細致的優(yōu)化后，收錄于我的新書《編程之法》第六章中，新書...
    Helen_Cat閱讀 7,591評論 1贊 39
  • （一）Java部分 1、列舉出JAVA中6個比較常用的包【天威誠信面試題】 【參考答案】 java.lang;ja...
    獨云閱讀 7,275評論 0贊 62
  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪：刷leetcod...
    土汪閱讀 12,931評論 0贊 33

友情鏈接更多精彩內(nèi)容