城市天際線道路升級，Leetcode 218.天際線問題

天際線問題

城市的天際線是從遠處觀看該城市中所有建筑物形成的輪廓的外部輪廓。現在，假設您獲得了城市風光照片（圖A）上顯示的所有建筑物的位置和高度，請編寫一個程序以輸出由這些建筑物形成的天際線（圖B）。

每個建筑物的幾何信息用三元組?[Li，Ri，Hi] 表示，其中 Li 和 Ri 分別是第 i 座建筑物左右邊緣的 x 坐標，Hi 是其高度。可以保證?0 ≤ Li, Ri ≤ INT_MAX,?0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您可以假設所有建筑物都是在絕對平坦且高度為 0 的表面上的完美矩形。

城市天際線道路升級、例如，圖A中所有建筑物的尺寸記錄為：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。

輸出是以?[ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的"關鍵點"（圖B中的紅點）的列表，它們唯一地定義了天際線。關鍵點是水平線段的左端點。請注意，最右側建筑物的最后一個關鍵點僅用于標記天際線的終點，并始終為零高度。此外，任何兩個相鄰建筑物之間的地面都應被視為天際線輪廓的一部分。

例如，圖B中的天際線應該表示為：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。

說明:

• 任何輸入列表中的建筑物數量保證在 [0, 10000]?范圍內。
• 輸入列表已經按升序排列在左邊的 x 位置 Li 。
• 輸出列表必須按 x 位排序。
• 輸出天際線中不得有連續的相同高度的水平線。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正確的答案；三條高度為 5 的線應該在最終輸出中合并為一個：[...[2 3], [4 5], [12 7], ...]

思路

城市天際線2什么時候出、如果按照一個矩形一個矩形來處理將會非常麻煩，我們可以把這些矩形拆成兩個點，一個左上頂點，一個右上頂點。將所有頂點按照橫坐標排序后，我們開始遍歷這些點。遍歷時，通過一個堆來得知當前圖形的最高位置。堆頂是所有頂點中最高的點，只要這個點沒被移出堆，說明這個最高的矩形還沒結束。對于左頂點，我們將其加入堆中。對于右頂點，我們找出堆中其相應的左頂點，然后移出這個左頂點，同時也意味這這個矩形的結束。具體代碼中，為了在排序后的頂點列表中區分左右頂點，左頂點的值是正數，而右頂點值則存的是負數。

注意

• 堆中先加入一個零點高度，幫助我們在只有最矮的建筑物時選擇最低值

復雜度

時間 O(NlogN) 空間 O(N)

?

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> height = new ArrayList<>();
        // 拆解矩形，構建頂點的列表
        for(int[] b:buildings) {
            // 左頂點存為負數
            height.add(new int[]{b[0], -b[2]});
            // 右頂點存為正數
            height.add(new int[]{b[1], b[2]});
        }
        // 根據橫坐標對列表排序，相同橫坐標的點縱坐標小的排在前面
        Collections.sort(height, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] != b[0]){
                    return a[0] - b[0];
                } else {
                    return a[1] - b[1];
                }
            }
        });
        // 構建堆，按照縱坐標來判斷大小
        Queue<Integer> pq = new PriorityQueue<Integer>(11, new Comparator<Integer>(){
            public int compare(Integer i1, Integer i2){
                return i2 - i1;
            }
        });
        // 將地平線值9先加入堆中
        pq.offer(0);
        // prev用于記錄上次keypoint的高度
        int prev = 0;
        for(int[] h:height) {
            // 將左頂點加入堆中
            if(h[1] < 0) {
                pq.offer(-h[1]);
            } else {
                // 將右頂點對應的左頂點移去
                pq.remove(h[1]);
            }
            int cur = pq.peek();
            // 如果堆的新頂部和上個keypoint高度不一樣，則加入一個新的keypoint
            if(prev != cur) {
                result.add(new int[]{h[0], cur});
                prev = cur;
            }
        }
        return result;
    }
}

?

?

?