Short and clean java solution(Heap and TreeMap)


  • 4
    M
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<int[]>();
        int n = buildings.length;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        TreeMap<Integer, Integer> treeMap = new TreeMap<Integer, Integer>();
        int pos = -1, curHeight = -1;
        while (pos+1 < n) {
            do {
                pos++;
                minHeap.add(buildings[pos][1]);
                treeMap.put(buildings[pos][2], buildings[pos][1]);
            } while (pos+1 < n && buildings[pos+1][0] == buildings[pos][0]); 
            int curMax = treeMap.lastKey();
            if (curMax != curHeight) {
                result.add(new int[] {buildings[pos][0], curHeight = curMax});
            }
            while (minHeap.size()!=0 && (pos == n-1 || minHeap.peek() < buildings[pos+1][0])) {
                int curpos = minHeap.poll();
                treeMap.values().remove(curpos);
                curMax = treeMap.size() == 0 ? 0 : treeMap.lastKey();
                if (curHeight != curMax ) {
                    result.add(new int[] {curpos, curHeight = curMax});
                }
            }
        }
        return result;
    }

Log in to reply
 

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