[数据结构与算法]力扣218. 天际线问题

力扣218. 天际线问题

对于开始点存正，结束点存负，然后存到相应的x坐标里，x坐标排序。然后遍历x坐标，对每个坐标单独处理最大值最小值即可。这里用了sortedmap省去了离散化

import java.util.SortedMap;
import java.util.TreeMap;
class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings){
        List<List<Integer>> res=new ArrayList<>();
        SortedMap<Integer,List<Integer>> map=new TreeMap<>();
        for(int[] build:buildings){
            List<Integer> list=map.getOrDefault(build[0],new ArrayList<>());
            list.add(build[2]);
            map.put(build[0],list);

            list=map.getOrDefault(build[1],new ArrayList<>());
            list.add(-build[2]);
            map.put(build[1],list);
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->(o2-o1));
        for(Integer i:map.keySet()){
            List<Integer> num=map.get(i);
            Integer top=queue.peek();
            for(int j:num){
                if(j>0)queue.add(j);
                else queue.remove(-j);
            }

            Integer newPeek = queue.peek();
            if(top == null || !top.equals(newPeek)){
                List<Integer> list = new ArrayList<>(2);
                list.add(i);
                list.add(newPeek == null ? 0 : newPeek);
                res.add(list);
            }
        }
        return res;
    }
}