亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Leetcode] The Skyline Problem 天際線問題

hidogs / 2102人閱讀

摘要：遍歷時(shí)，通過一個(gè)堆來得知當(dāng)前圖形的最高位置。堆頂是所有頂點(diǎn)中最高的點(diǎn)，只要這個(gè)點(diǎn)沒被移出堆，說明這個(gè)最高的矩形還沒結(jié)束。對(duì)于左頂點(diǎn)，我們將其加入堆中。

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], ...]
排序+堆 復(fù)雜度

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

思路

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

注意

堆中先加入一個(gè)零點(diǎn)高度，幫助我們?cè)谥挥凶畎慕ㄖ飼r(shí)選擇最低值

代碼 
public class Solution {
    public List getSkyline(int[][] buildings) {
        List result = new ArrayList<>();
        List height = new ArrayList<>();
        // 拆解矩形，構(gòu)建頂點(diǎn)的列表
        for(int[] b:buildings) {
            // 左頂點(diǎn)存為負(fù)數(shù)
            height.add(new int[]{b[0], -b[2]});
            // 右頂點(diǎn)存為正數(shù)
            height.add(new int[]{b[1], b[2]});
        }
        // 根據(jù)橫坐標(biāo)對(duì)列表排序，相同橫坐標(biāo)的點(diǎn)縱坐標(biāo)小的排在前面
        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];
                }
            }
        });
        // 構(gòu)建堆，按照縱坐標(biāo)來判斷大小
        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) {
            // 將左頂點(diǎn)加入堆中
            if(h[1] < 0) {
                pq.offer(-h[1]);
            } else {
            // 將右頂點(diǎn)對(duì)應(yīng)的左頂點(diǎn)移去
                pq.remove(h[1]);
            }
            int cur = pq.peek();
            // 如果堆的新頂部和上個(gè)keypoint高度不一樣，則加入一個(gè)新的keypoint
            if(prev != cur) {
                result.add(new int[]{h[0], cur});
                prev = cur;
            }
        }
        return result;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64567.html

相關(guān)文章

  • LeetCode[218] The Skyline Problem

    摘要：復(fù)雜度思路利用的思想，先分成左右兩部分，再進(jìn)行。每次都要將的左上角和右下角推進(jìn)，進(jìn)行計(jì)算。觀察左邊和右邊進(jìn)行。 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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Jump Game I & II

    摘要：建立動(dòng)規(guī)數(shù)組，表示從起點(diǎn)處到達(dá)該點(diǎn)的可能性。循環(huán)結(jié)束后，數(shù)組對(duì)所有點(diǎn)作為終點(diǎn)的可能性都進(jìn)行了賦值。和的不同在于找到最少的步數(shù)。此時(shí)的一定是滿足條件的最小的，所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

    rose 評(píng)論0 收藏0

  • [LeetCode] Palindrome Number

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

    劉厚水 評(píng)論0 收藏0

  • [LeetCode] 4Sum & 4Sum II

    摘要：和方法一樣，多一個(gè)數(shù)，故多一層循環(huán)。完全一致，不再贅述， 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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Sliding Window Maximum/Median

    摘要：窗口前進(jìn)，刪隊(duì)首元素保證隊(duì)列降序加入當(dāng)前元素下標(biāo)從開始，每一次循環(huán)都將隊(duì)首元素加入結(jié)果數(shù)組 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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<