Java solution using TreeMap to keep track of active building's <ri,hi> pair


  • 0
    L
    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> res = new ArrayList<int[]>();
            TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>(); //key is ri, value is hi.
            List<int[]> roundRes = new ArrayList<int[]>();
            for(int i=0;i<buildings.length;i++){
                int maxHeight = 0;
                Integer tail = map.isEmpty()?null:map.lastKey();
                while(tail!=null&&tail>=buildings[i][0]) {
                    if(map.get(tail)>maxHeight) maxHeight = map.get(tail);
                    tail = map.lowerKey(tail);
                }
                if(buildings[i][2]>maxHeight) { //current building's hi > all the buildings whose ri is on the right of curr's left, add curr li
                    if(!res.isEmpty()&&res.get(res.size()-1)[0]==buildings[i][0]&&res.get(res.size()-1)[1]<buildings[i][2]){
                        //two buildings with same li, and latter one is higher. remove the key point add by pre building.
                        res.remove(res.size()-1); 
                    }
                    int[] liToAdd = {buildings[i][0],buildings[i][2]};
                    roundRes.add(liToAdd);
                }
                while(tail!=null){ //tail is the largest ri smaller than buildings[i][0]
                    if(map.get(tail)>maxHeight){
                        int[] riToAdd = {tail,maxHeight};
                        roundRes.add(0,riToAdd);
                        maxHeight = map.get(tail);
                    }
                    map.remove(tail);
                    tail = map.lowerKey(tail);
                }
                res.addAll(roundRes);
                roundRes.clear();
                if(!map.containsKey(buildings[i][1])||map.get(buildings[i][1])<buildings[i][2]){
                    map.put(buildings[i][1],buildings[i][2]);
                }
            }
            int maxHeight = 0;
            Integer tail = map.isEmpty()?null:map.lastKey();
            while(tail!=null){ //tail is the largest ri smaller than buildings[i][0]
                if(map.get(tail)>maxHeight){
                    int[] riToAdd = {tail,maxHeight};
                    roundRes.add(0,riToAdd);
                    maxHeight = map.get(tail);
                }
                map.remove(tail);
                tail = map.lowerKey(tail);
            }
            res.addAll(roundRes);
            return res;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.