easy to understand, O(nlogn) java solution with detailed explanation


  • 3
    B

    The idea is inspired by this posts https://discuss.leetcode.com/topic/28482/once-for-all-explanation-with-clean-java-code-o-n-2-time-o-n-space/2
    The basic idea is that the the change of contour only happens at each breaking points where previous highest building no longer shadow the current building. Therefore, I use a class called breaking points. We only care about the start point. We have our current x which start from most left point.And we scan from left to right. Once we saw a start point, we put that in our heap, we do this because we know, this building is starting to take effect on our contour. Whenever we encounter a point, no matter what kind of point it is, we advance our current x.And Whenever we encounter a point, we need to check the current max height. If it changes, it need to add it to our final ans. But here comes the question. How do we know, if its effect expires? Since we have record its ending x and we know our current x.It is very easy to check if it expires(you could get it in the code).
    So the steps are:

    1. build our breaking points
    2. sort them according to certain rule (plz pay attention to this part in the code!)
    3. scan the points from left to right
      4.when scanning, remove the expires point if necessary, we don't care if there is other expired point in our heap as long as it does not affect our solution.
      5.if height changes, add it to the final solution.

    Here comes the Analysis of the algorithm:

    1. first sort. It takes O(nlogn)
    2. add points to the heap and remove the top points. worst case nlogn
      So the overall it is O(nlogn).
    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<breakPoint> points = new ArrayList<>();
            List<int[]> ans = new ArrayList<>();
            for (int[] building : buildings){
                points.add(new breakPoint(building[0], building[1], true, building[2]));
                points.add(new breakPoint(building[1], building[1], false, building[2]));
            }
            Collections.sort(points, new sortComparator());
            PriorityQueue<breakPoint> maxHeap = new PriorityQueue<>(new heapComparator());
            int curX = 0;
            int preHeight = 0;
            for (breakPoint point : points){
                if (point.isStart){
                    maxHeap.offer(point);
                }
                curX = point.x;
                while (!maxHeap.isEmpty() && maxHeap.peek().end <= curX){
                    maxHeap.poll();
                }
                int curMaxHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek().height;
                if (preHeight != curMaxHeight){
                    ans.add(new int[]{curX, curMaxHeight});
                }
                preHeight = curMaxHeight;
            }
            return ans;
        }
        class sortComparator implements Comparator<breakPoint>{
            @Override
            public int compare(breakPoint o1, breakPoint o2){
                if (o1.x != o2.x){
                    return Integer.compare(o1.x, o2.x);
                }else{
                    if (o1.isStart && o2.isStart){
                        return Integer.compare(o2.height, o1.height);
                    }else {
                        return o1.isStart ? -1 : 1;
                    }
                }
            }
        }
        class heapComparator implements  Comparator<breakPoint>{
            @Override
            public int compare(breakPoint o1, breakPoint o2){
                return Integer.compare(o2.height, o1.height);
            }
        }
        class breakPoint{
            int x;
            int end;
            boolean isStart;
            int height;
            public breakPoint(int x, int end, boolean isStart, int height){
                this.x = x;
                this.end = end;
                this.isStart = isStart;
                this.height = height;
            }
        }
    }
    

  • 0
    H

    nice solution
    very insightful


Log in to reply
 

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