国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] The Skyline Problem 天際線問題

hidogs / 2056人閱讀

摘要：遍歷時，通過一個堆來得知當前圖形的最高位置。堆頂是所有頂點中最高的點，只要這個點沒被移出堆，說明這個最高的矩形還沒結束。對于左頂點，我們將其加入堆中。

The Skyline Problem 
A city"s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).


 Buildings  Skyline Contour The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.


For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .


The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.


For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].


Notes:


The number of buildings in any input list is guaranteed to be in the range [0, 10000]. The input list is already sorted in ascending order by the left x position Li. The output list must be sorted by the x position. There must be no consecutive horizontal lines of equal
height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
排序+堆 復雜度

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

思路

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

注意

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

代碼 
public class Solution {
    public List getSkyline(int[][] buildings) {
        List result = new ArrayList<>();
        List 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(){
            public int compare(int[] a, int[] b){
                if(a[0] != b[0]){
                    return a[0] - b[0];
                } else {
                    return a[1] - b[1];
                }
            }
        });
        // 構建堆，按照縱坐標來判斷大小
        Queue pq = new PriorityQueue(11, new Comparator(){
            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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64567.html

相關文章

  • LeetCode[218] The Skyline Problem

    摘要：復雜度思路利用的思想，先分成左右兩部分，再進行。每次都要將的左上角和右下角推進，進行計算。觀察左邊和右邊進行。 LeetCode[218] The Skyline Problem A citys skyline is the outer contour of the silhouette formed by all the buildings in that city when vie...

    keithyau 評論0 收藏0

  • [LintCode/LeetCode] Jump Game I & II

    摘要：建立動規數組，表示從起點處到達該點的可能性。循環結束后，數組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數。此時的一定是滿足條件的最小的，所以一定是最優解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

    rose 評論0 收藏0

  • [LeetCode] Palindrome Number

    摘要：逐位看官，這兩種解法一看便知，小子便不多費唇舌了。字符數組比較法原數翻轉比較法 Problem Determine whether an integer is a palindrome. Do this without extra space. click to show spoilers. Some hints:Could negative integers be palindrom...

    劉厚水 評論0 收藏0

  • [LeetCode] 4Sum & 4Sum II

    摘要：和方法一樣，多一個數，故多一層循環。完全一致，不再贅述， 4Sum Problem Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which ...

    sydMobile 評論0 收藏0

  • [LintCode/LeetCode] Sliding Window Maximum/Median

    摘要：窗口前進，刪隊首元素保證隊列降序加入當前元素下標從開始，每一次循環都將隊首元素加入結果數組 Sliding Window Maximum Problem Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration fro...

    crelaber 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<