218. The Skyline Problem

Link

Solution

想法是依照x軸大小，巡禮每個building point透過比較height最大值的變化來產生figure point

更新height max的時機，當進入新的building 區間 (start point)，或離開某個building區間(end point)

進入新的building區間時，要把新的building height加入比較看看是否會取代成為maxheight 反之離開舊的building區間時，要移除舊的building height看看否maxheight有變化。

滿足這樣找出最大，且能刪除加入的queue，只有priorityQueue，但因為我們要刪除、加入都能有logN的時間複雜度。所以選用treeMap。

當height max值被更動了，那產生的figure point ( x, currentHeight)

https://www.youtube.com/watch?time_continue=789&v=GSBLe8cKu0s&feature=emb_title

 public static List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> ret = new LinkedList<>();
        BuildingPoint[] buildingPoints = new BuildingPoint[buildings.length * 2];
//        Arrays.stream(buildings).forEach(a -> {
//            Arrays.stream(a).mapToObj(b -> b + ",").forEach(System.out::print);
//            System.out.println("");
//        });
        int index = 0;
        for (int[] building : buildings) {
            buildingPoints[index] = new BuildingPoint(building[0], building[2], true);
            buildingPoints[index + 1] = new BuildingPoint(building[1], building[2], false);
            index += 2;
        }
        Arrays.sort(buildingPoints);

        TreeMap<Integer, Integer> queue = new TreeMap<>();// key: height, value : count
        queue.put(0, 1);
        int prevouisMax = 0;
        for (BuildingPoint buildingPoint : buildingPoints) {
            if (buildingPoint.isStart) {
                queue.compute(buildingPoint.height, (k, v) -> {
                    if (v == null) return 1;
                    else return v + 1;
                });
            } else {
                queue.compute(buildingPoint.height, (k, v) -> {
                    if (v == 1) return null;
                    else return v - 1;
                });
            }
            int maxCurrent = queue.lastKey();
            if (prevouisMax != maxCurrent) {
                ret.add(Arrays.asList(new Integer[]{buildingPoint.x, maxCurrent}));
                prevouisMax = maxCurrent;
            }
        }

        return ret;
    }

    public static class BuildingPoint implements Comparable<BuildingPoint> {
        public int x;
        public int height;
        public boolean isStart;


        BuildingPoint(int x, int height, boolean isStart) {
            this.x = x;
            this.height = height;
            this.isStart = isStart;
        }

        @Override
        public int compareTo(BuildingPoint o) {
            if (o.x != x) {
                return x - o.x;
            } else {
                //edge cases
                if (isStart && o.isStart) {
                    //handle the higher height fist
                    //thus, the higher high one is smaller
                    return o.height - height;
                } else if (!isStart && !o.isStart) {
                    //handle the lower height first
                    //thus, the lower height is smaller
                    return height - o.height;
                } else {
                    // shall always handle start first
                    return isStart ? 1 : 2;
                }
            }
        }