本文涉及知識點

堆 （優先隊列) 掃描線

LeetCode218. 天際線問題

城市的 天際線 是從遠處觀看該城市中所有建筑物形成的輪廓的外部輪廓。給你所有建筑物的位置和高度，請返回 由這些建筑物形成的 天際線 。
每個建筑物的幾何信息由數組 buildings 表示，其中三元組 buildings[i] = [lefti, righti, heighti] 表示：
lefti 是第 i 座建筑物左邊緣的 x 坐標。
righti 是第 i 座建筑物右邊緣的 x 坐標。
heighti 是第 i 座建筑物的高度。
你可以假設所有的建筑都是完美的長方形，在高度為 0 的絕對平坦的表面上。
天際線 應該表示為由 “關鍵點” 組成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐標 進行 排序 。關鍵點是水平線段的左端點。列表中最后一個點是最右側建筑物的終點，y 坐標始終為 0 ，僅用于標記天際線的終點。此外，任何兩個相鄰建筑物之間的地面都應被視為天際線輪廓的一部分。
注意：輸出天際線中不得有連續的相同高度的水平線。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正確的答案；三條高度為 5 的線應該在最終輸出中合并為一個：[…[2 3], [4 5], [12 7], …]

示例 1：

輸入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
輸出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解釋：
圖 A 顯示輸入的所有建筑物的位置和高度，
圖 B 顯示由這些建筑物形成的天際線。圖 B 中的紅點表示輸出列表中的關鍵點。
示例 2：

輸入：buildings = [[0,2,3],[2,5,3]]
輸出：[[0,3],[5,0]]

提示：

1 <= buildings.length <= 10⁴
0 <= lefti < righti <= 2³¹ - 1
1 <= heighti <= 2³¹ - 1
buildings 按 lefti 非遞減排序

懶刪除堆+ 掃描線

通過觀察示例，我們可以得出如下結論：
性質一：關鍵點的橫坐標一定是建筑的左右邊緣。令建筑的左右邊緣的集合是xs。
性質二：xs中除以下元素外，全部是關鍵點：
$?$x,i ,其中 x$\in$xs。 x in $[lefti,righti] x對應的height 小于等于heighti。
性質三：根據性質二，一個x對應多個height，取最大值。xh記錄x及對應高度。
性質四：根據性質三，性質二可以簡化為 x in $(lefti,righti)
lh 記錄左邊界及高度。
rh記錄有邊界及高度。
xh、lh、rh都按x的升序排序。
有序mulset has代替懶刪除堆 記錄：
lefti < x ,righti > x的高度。 如果高度的最大值小于x對應的高度，則是關鍵點。

關鍵點的縱坐標y
$$\{\begin{array}{llc}0& & 不存在lefti小于等于x,righti大于x的建筑\\ 這些建筑的最大高度& & other\end{array}$$
如果兩個相鄰的關鍵點高度相同，刪除前面的關鍵點。

代碼

核心代碼

  class Solution {public:vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {vector<pair<int, int>> tmp,xh, lh, rh;for (const auto& v : buildings) {lh.emplace_back(make_pair(v[0], v[2]));rh.emplace_back(make_pair(v[1], v[2]));}tmp = lh;tmp.insert(tmp.end(), rh.begin(), rh.end());sort(tmp.begin(), tmp.end());sort(rh.begin(), rh.end());		 for (const auto& [x, h] : tmp) {if (xh.size() && (xh.back().first == x)) {xh.back().second = h;}else {xh.emplace_back(make_pair(x, h));}}multiset<int> has;int il = 0, ir = 0;vector<vector<int>> ret;for (const auto& [x, h] : xh) {			 while ((il < lh.size() )&& (lh[il].first < x)) {has.emplace(lh[il++].second);}while ((ir < rh.size()) && (rh[ir].first <= x)) {has.erase(has.find(rh[ir].second));ir++;}if (has.empty() || (*has.rbegin() < h)) {ret.emplace_back(vector<int>{ x,-1 });}while ((il < lh.size()) && (lh[il].first <= x)) {has.emplace(lh[il++].second);}ret.back()[1] = has.empty()?0: *has.rbegin();	 }		vector < vector<int>> ret2 = { ret[0] };for (int i = 1; i < ret.size(); i++) {if (ret2.back()[1] != ret[i][1]) {ret2.emplace_back(ret[i]);}}return ret2;}};

單元測試

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{	vector<vector<int>> buildings;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){buildings = { {2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8} };auto res = Solution().getSkyline(buildings);AssertV2(vector<vector<int>>{ {2, 10}, { 3,15 }, { 7,12 }, { 12,0 }, { 15,10 }, { 20,8 }, { 24,0 }}, res);}TEST_METHOD(TestMethod01){buildings = { {0,2,3},{2,5,3} }		;auto res = Solution().getSkyline(buildings);AssertV2(vector<vector<int>>{ {0, 3}, { 5,0 }}, res);}};
}

簡化思路

所有x都是關鍵點，除非y和前一個x相同。
y = max(所有左邊界 <= x，右邊界大于x的建筑高度)，所有沒有符合的建筑y為0。

class Solution {
public:vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {vector<pair<int, int>> tmp, xh, lh, rh;for (const auto& v : buildings) {lh.emplace_back(make_pair(v[0], v[2]));rh.emplace_back(make_pair(v[1], v[2]));}tmp = lh;tmp.insert(tmp.end(), rh.begin(), rh.end());sort(tmp.begin(), tmp.end());sort(rh.begin(), rh.end());for (const auto& [x, h] : tmp) {if (xh.size() && (xh.back().first == x)) {xh.back().second = h;}else {xh.emplace_back(make_pair(x, h));}}multiset<int> has;int il = 0, ir = 0;vector<vector<int>> ret;for (const auto& [x, h] : xh) {while ((il < lh.size()) && (lh[il].first <= x)) {has.emplace(lh[il++].second);}while ((ir < rh.size()) && (rh[ir].first <= x)) {has.erase(has.find(rh[ir].second));ir++;}int y = has.empty() ? 0 : *has.rbegin();if (ret.empty() || (ret.back()[1] != y)) {ret.emplace_back(vector<int>{x, y});}}return ret;}
};

擴展閱讀

視頻課程

先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

相關推薦

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結為主。
按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
有效學習：明確的目標 及時的反饋 拉伸區（難度合適） 專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。