城市的天際線是從遠(yuǎn)處觀看該城市中所有建筑物形成的輪廓的外部輪廓。給你所有建筑物的位置和高度，請(qǐng)返回由這些建筑物形成的 天際線 。

每個(gè)建筑物的幾何信息由數(shù)組 buildings 表示，其中三元組 buildings[i] = [lefti, righti, heighti] 表示：

• lefti 是第 i 座建筑物左邊緣的 x 坐標(biāo)。
• righti 是第 i 座建筑物右邊緣的 x 坐標(biāo)。
• heighti 是第 i 座建筑物的高度。

天際線 應(yīng)該表示為由 “關(guān)鍵點(diǎn)” 組成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐標(biāo) 進(jìn)行 排序 。關(guān)鍵點(diǎn)是水平線段的左端點(diǎn)。列表中最后一個(gè)點(diǎn)是最右側(cè)建筑物的終點(diǎn)，y 坐標(biāo)始終為 0 ，僅用于標(biāo)記天際線的終點(diǎn)。此外，任何兩個(gè)相鄰建筑物之間的地面都應(yīng)被視為天際線輪廓的一部分。

注意：輸出天際線中不得有連續(xù)的相同高度的水平線。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正確的答案；三條高度為 5 的線應(yīng)該在最終輸出中合并為一個(gè)：[…[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 中的紅點(diǎn)表示輸出列表中的關(guān)鍵點(diǎn)。 示例 2：輸入：buildings = [[0,2,3],[2,5,3]] 輸出：[[0,3],[5,0]]

解題思路

通過觀察我們可以得出

• 關(guān)鍵點(diǎn)總是來源于建筑物的左邊緣或者右邊緣的
• 相鄰兩個(gè)關(guān)鍵點(diǎn)之間必定存在高度差
  因此，我們可以只對(duì)所有建筑物的左右邊緣進(jìn)行遍歷，關(guān)鍵點(diǎn)只在這些點(diǎn)當(dāng)中產(chǎn)生

因?yàn)樽罱K結(jié)果的關(guān)鍵點(diǎn)需要按照x坐標(biāo)進(jìn)行排序，因此我們先對(duì)所有建筑物的左右端點(diǎn)按x坐標(biāo)進(jìn)行一次統(tǒng)一的從小到大的排序，x坐標(biāo)相同的話，按高度從小到大的排序

為了區(qū)分建筑物的左右端點(diǎn)，我們可以用負(fù)數(shù)表示左端點(diǎn)的高度，正數(shù)表示右端點(diǎn)的高度

假設(shè)遍歷到某個(gè)端點(diǎn)cur，大頂堆中存放的是：該端點(diǎn)處于的x坐標(biāo)，被若干個(gè)建筑物

例如，x=7時(shí)，存儲(chǔ)的就是3個(gè)建筑物的高度，因?yàn)楫?dāng)前遍歷的是紅色建筑物的右端點(diǎn)，因此在當(dāng)前x=7的坐標(biāo)下，已經(jīng)不被覆蓋了，所以是2個(gè)建筑物的高度，而這兩個(gè)建筑物的最大高度是12，和之前關(guān)鍵點(diǎn)的最大高度不一致，因此可以判斷出現(xiàn)了關(guān)鍵點(diǎn)

總結(jié)

簡(jiǎn)單來說，在遍歷端點(diǎn)的過程中，通過高度的正負(fù)來實(shí)現(xiàn)對(duì)建筑物左右端點(diǎn)的判斷，遍歷到左端點(diǎn)則進(jìn)入優(yōu)先隊(duì)列，說明后面的若干個(gè)x坐標(biāo)都被當(dāng)前高度為h的建筑物覆蓋，遍歷到右端點(diǎn)則退出優(yōu)先隊(duì)列，說明后面的所有x坐標(biāo)都不會(huì)被當(dāng)前高度為h的建筑物覆蓋。所以通過優(yōu)先隊(duì)列，我們就可以知道，當(dāng)前的端點(diǎn)的x坐標(biāo)覆蓋了多少個(gè)建筑物，因?yàn)樽罡叩慕ㄖ飼?huì)遮蓋其他低的建筑物，所以我們維護(hù)的是一個(gè)大頂堆。

又因?yàn)殛P(guān)鍵點(diǎn)和前一個(gè)關(guān)鍵點(diǎn)的高度必然是不一樣的，所以只要當(dāng)前的堆頂元素和前一個(gè)關(guān)鍵點(diǎn)的高度不一樣，我們就可以判斷當(dāng)前x坐標(biāo)也是一個(gè)關(guān)鍵點(diǎn)

代碼

class Solution {public List<List<Integer>> getSkyline(int[][] buildings) {List<List<Integer>> res=new ArrayList<>();List<int[]> cnt=new ArrayList<>();for (int[] building : buildings) {cnt.add(new int[]{building[0],-building[2]});cnt.add(new int[]{building[1],building[2]});}int i=0,pre=0;Collections.sort(cnt,(o1, o2) -> o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);PriorityQueue<Integer>priorityQueue=new PriorityQueue<>((o1, o2) -> o2-o1);priorityQueue.add(0);for (int[] cur : cnt) {if(cur[1]<0){priorityQueue.add(-cur[1]);}else{priorityQueue.remove(cur[1]);}int h=priorityQueue.peek();if(h!=pre){res.add(Arrays.asList(cur[0],h));pre=h;}}return res;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 218. 天际线问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。