Share my ac java code, easy to understand


  • 0
    E

    public class Solution {

    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> skyline = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0) {
            return skyline;
        }
        Arrays.sort(buildings, new Comparator<int[]>() {
           public int compare(int[] building1, int[] building2) {
               if (building1[0] < building2[0]) { return -1; }
               if (building1[0] > building2[0]) { return 1; } 
               if (building1[1] < building2[1]) { return -1; }
               if (building1[1] > building2[1]) { return 1; }
               if (building1[2] < building2[2]) { return -1; }
               if (building1[2] > building2[2]) { return 1; }
               return 0;
           } 
        });
        return drawSkyline(buildings, 0, buildings.length - 1);
    }
    private List<int[]> drawSkyline(int[][] buildings, int start, int end) {
        List<int[]> skyline = new ArrayList<int[]>();
        if (start == end) {
            skyline.add(new int[]{ buildings[start][0], buildings[start][2] });
            skyline.add(new int[]{ buildings[end][1], 0 });
            return skyline;
        }
        int mid = start + (end - start) / 2;
        List<int[]> leftSky = drawSkyline(buildings, start, mid);
        List<int[]> rightSky = drawSkyline(buildings, mid + 1, end);
        skyline = merge(leftSky, rightSky);
        return skyline;
    }
    private List<int[]> merge(List<int[]> leftSky, List<int[]> rightSky) {
        List<int[]> skyline = new ArrayList<int[]>();
        int leftIndex = 0;
        int rightIndex = 0;
        int[] lastLeft = new int[]{ 0, 0 };
        int[] lastRight = new int[]{ 0, 0 };
        while (leftIndex < leftSky.size() && rightIndex < rightSky.size()) {
            int[] leftPoint = leftSky.get(leftIndex);
            int[] rightPoint = rightSky.get(rightIndex);
            int whichIsHigher = lastLeft[1] < lastRight[1] ? 2 : (lastLeft[1] == lastRight[1] ? 0 : 1); 
            if (leftPoint[0] == rightPoint[0]) {
                int currentHeight = Math.max(leftPoint[1], rightPoint[1]);
                if (currentHeight == Math.max(lastRight[1], lastLeft[1])) {
                } else {
                    skyline.add(new int[]{ leftPoint[0], currentHeight });
                }
                lastLeft = leftPoint;
                lastRight = rightPoint;
                leftIndex ++;
                rightIndex ++;
            } else if (leftPoint[0] < rightPoint[0]) {
                switch(whichIsHigher) {
                    case 0 :
                        if (leftPoint[1] > lastLeft[1]) {
                            skyline.add(leftPoint);
                        }
                        break;
                    case 1 :
                        if (leftPoint[1] == lastLeft[1]) {
                        } else if (leftPoint[1] < lastRight[1]) {
                            skyline.add(new int[]{ leftPoint[0], lastRight[1] });
                        } else {
                            skyline.add(leftPoint);
                        }
                        break;
                    case 2 :
                        if (leftPoint[1] <= lastRight[1]) {
                        } else {
                            skyline.add(leftPoint);
                        }
                }
                lastLeft = leftPoint;
                leftIndex ++;
            } else {
                switch(whichIsHigher) {
                    case 0 :
                        if (rightPoint[1] > lastRight[1]) {
                            skyline.add(rightPoint);
                        }
                        break;
                    case 2 :
                        if (rightPoint[1] == lastRight[1]) {
                        } else if (rightPoint[1] < lastLeft[1]) {
                            skyline.add(new int[]{ rightPoint[0], lastLeft[1] });
                        } else {
                            skyline.add(rightPoint);
                        }
                        break;
                    case 1 :
                        if (rightPoint[1] <= lastLeft[1]) {
                        } else {
                            skyline.add(rightPoint);
                        }
                }
                lastRight = rightPoint;
                rightIndex ++;
            }
        }
        while (leftIndex < leftSky.size()) {
            int[] leftPoint = leftSky.get(leftIndex);
            skyline.add(leftPoint);
            leftIndex++;
        }
        while (rightIndex < rightSky.size()) {
            int[] rightPoint = rightSky.get(rightIndex);
            skyline.add(rightPoint);
            rightIndex++;
        }
        return skyline;
    }
    

    }


Log in to reply
 

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