LeetCode 218. 天际线问题

迷南。 2022-10-28 10:12 182阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]  
[大佬题解][Link 1]

//解法一：优先队列（PriorityQueue）
    class Solution {
        
        public List<List<Integer>> getSkyline(int[][] buildings) {
        
            List<List<Integer>> points = new ArrayList<>();
            List<List<Integer>> results = new ArrayList<>();
            int n = buildings.length;
            //求出左上角和右上角坐标，左上角坐标y存负数
            for(int[] b : buildings){
        
                List<Integer> p1 = new ArrayList<>();
                p1.add(b[0]);
                p1.add(-b[2]);
                points.add(p1);
    
                List<Integer> p2 = new ArrayList<>();
                p2.add(b[1]);
                p2.add(b[2]);
                points.add(p2);
            }
            Collections.sort(points, new Comparator<List<Integer>>(){
        
                public int compare(List<Integer> p1, List<Integer> p2){
        
                    int x1 = p1.get(0);
                    int y1 = p1.get(1);
                    int x2 = p2.get(0);
                    int y2 = p2.get(1);
                    if(x1 != x2){
        
                        return x1 - x2;
                    }else{
        
                        return y1 - y2;
                    }
                }
            });
            Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
        
                public int compare(Integer i1, Integer i2){
        
                    return i2 - i1;
                }
            });
            queue.offer(0);
            int preMax = 0;
            for(List<Integer> p : points){
        
                int x = p.get(0);
                int y = p.get(1);
                if(y < 0){
        
                    queue.offer(-y);
                }else{
        
                    queue.remove(y);
                }
                int curMax = queue.peek();
                if(curMax != preMax){
        
                    List<Integer> temp = new ArrayList<>();
                    temp.add(x);
                    temp.add(curMax);
                    results.add(temp);
                    preMax = curMax;
                }
            }
            return results;
        }
    }

//解法二：优先队列（TreeMap）
    public List<List<Integer>> getSkyline(int[][] buildings) {
        
       List<List<Integer>> points = new ArrayList<>();
        List<List<Integer>> results = new ArrayList<>();
        int n = buildings.length;
        //求出将左上角和右上角坐标, 左上角坐标的 y 存负数
        for (int[] b : buildings) {
        
            List<Integer> p1 = new ArrayList<>();
            p1.add(b[0]);
            p1.add(-b[2]);
            points.add(p1);
    
            List<Integer> p2 = new ArrayList<>();
            p2.add(b[1]);
            p2.add(b[2]);
            points.add(p2);
        }
        //将所有坐标排序
        Collections.sort(points, new Comparator<List<Integer>>() {
        
            @Override
            public int compare(List<Integer> p1, List<Integer> p2) {
        
                int x1 = p1.get(0);
                int y1 = p1.get(1);
                int x2 = p2.get(0);
                int y2 = p2.get(1);
                if (x1 != x2) {
        
                    return x1 - x2;
                } else {
        
                    return y1 - y2;
                }
            }
    
        });
        TreeMap<Integer, Integer> treeMap = new TreeMap<>(new Comparator<Integer>() {
        
            @Override
            public int compare(Integer i1, Integer i2) {
        
                return i2 - i1;
            }
        });
        treeMap.put(0, 1);
        int preMax = 0;
    
        for (List<Integer> p : points) {
        
            int x = p.get(0);
            int y = p.get(1);
            if (y < 0) {
        
                Integer v = treeMap.get(-y);
                if (v == null) {
        
                    treeMap.put(-y, 1);
                } else {
        
                    treeMap.put(-y, v + 1);
                }
            } else {
        
                Integer v = treeMap.get(y);
                if (v == 1) {
        
                    treeMap.remove(y);
                } else {
        
                    treeMap.put(y, v - 1);
                }
            }
            int curMax = treeMap.firstKey();
            if (curMax != preMax) {
        
                List<Integer> temp = new ArrayList<>();
                temp.add(x);
                temp.add(curMax);
                results.add(temp);
                preMax = curMax;
            }
        }
        return results;
    }

//解法三：分治最快
    class Solution {
        
        public List<List<Integer>> getSkyline(int[][] buildings) {
        
        if(buildings.length == 0){
        
            return  new ArrayList<>();
        }
        return merge(buildings, 0, buildings.length - 1);
    }
    
    private List<List<Integer>> merge(int[][] buildings, int start, int end) {
        
    
        List<List<Integer>> res = new ArrayList<>();
        //只有一个建筑, 将 [x, h], [y, 0] 加入结果
        if (start == end) {
        
            List<Integer> temp = new ArrayList<>();
            temp.add(buildings[start][0]);
            temp.add(buildings[start][2]);
            res.add(temp);
    
            temp = new ArrayList<>();
            temp.add(buildings[start][1]);
            temp.add(00);
            res.add(temp);
            return res;
        }
        int mid = (start + end) >>> 1;
        //第一组解
        List<List<Integer>> Skyline1  = merge(buildings, start, mid);
        //第二组解
        List<List<Integer>> Skyline2  = merge(buildings, mid + 1, end);
        //下边将两组解合并
        int h1 = 0;
        int h2 = 0;
        int i = 0;
        int j = 0;
        while (i < Skyline1 .size() || j < Skyline2 .size()) {
        
            long x1 = i < Skyline1 .size() ? Skyline1 .get(i).get(0) : Long.MAX_VALUE;
            long x2 = j < Skyline2 .size() ? Skyline2 .get(j).get(0) : Long.MAX_VALUE;
            long x = 0;
            //比较两个坐标
            if (x1 < x2) {
        
                h1 = Skyline1 .get(i).get(1);
                x = x1;
                i++;
            } else if (x1 > x2) {
        
                h2 = Skyline2 .get(j).get(1);
                x = x2;
                j++;
            } else {
        
                h1 = Skyline1 .get(i).get(1);
                h2 = Skyline2 .get(j).get(1);
                x = x1;
                i++;
                j++;
            }
            //更新 height
            int height = Math.max(h1, h2);
            //重复的解不要加入
            if (res.isEmpty() || height != res.get(res.size() - 1).get(1)) {
        
                List<Integer> temp = new ArrayList<>();
                temp.add((int) x);
                temp.add(height);
                res.add(temp);
            }
        }
        return res;
    }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/64436c312c25443889ec871f3ef0d192.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221024/55ee1f4bbac940ed8c6165eb628a661c.png
[Link 1]: https://leetcode-cn.com/problems/the-skyline-problem/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--45/