Leetcode 218. The Skyline Problem

원제 설명 이 길 어서 링크 를 놓 습 니 다:https://leetcode.com/problems/the-skyline-problem/description/
사고방식: 제목 은 모든 건축 여정 의 윤곽 을 요구 하고 고도 로 변화 하 는 점 을 제시 하면 된다.폭력 적 인 방법 은 모든 건축 의 좌우 경 계 를 구하 고 이 범 위 를 옮 겨 다 니 며 각 점 에서 현재 의 최고 치 를 찾 아 앞의 최고 치 와 같 으 면 건 너 뜁 니 다.
최 적 화 된 해법 은 다른 인터넷 의 해답 을 참고 하 는 것 이 고 다음은 자신 이 다 한 후의 사고 이다.위의 알고리즘 은 두 가지 문제 가 있 습 니 다.
4. 567917. 어떤 점 은 높이 를 찾 을 필요 가 없다. 왜냐하면 그것 은 건축물 의 높이 변화 가 있 는 곳 이 아니 기 때문이다
4. 567917. 건축물 의 높이 변화 가 있 는 곳 에서 모든 건축물 을 옮 겨 다 녔 다. 만약 에 데이터 구조 가 현재 의 최대 높이 를 직접 구 할 수 있다 면 시간 복잡 도 는 작 아 지고 이 데이터 구 조 는 바로 쌓 인 것 이다
첫 번 째 단 계 는 하나의 list 로 모든 건축물 의 높이 가 변화 하 는 점 을 저장 하고 좌표 와 높이 를 기록 한 다음 에 좌 표를 누 른 다음 에 높이 에 따라 정렬 해 야 한다. 후속 적 으로 쌓 인 처 리 를 위해 건축 기점 의 높이 를 마이너스 로 기록 하고 종점 은 양수 로 기록 해 야 한다.
두 번 째 단 계 는 최대 더 미 를 초기 화 합 니 다. (더 미 는 항상 현재 더 미 를 유지 하고 있 습 니 다) 우 리 는 위의 list 를 옮 겨 다 니 며 모든 요 소 를 최대 높이 로 변화 시 키 면 이것 은 윤곽 변화 점 이 므 로 결과 집중 에 추가 해 야 합 니 다.구체 적 으로 말 하면 모든 요소 에 대해 출발점 이 라면 이 높이 를 더미 안에 넣 고 이전에 한 마이너스 값 을 다시 마이너스 로 해 야 한다.종점 이 라면 이 건물 이 여기 서 사라 진 다 는 것 을 증명 하기 위해 서 는 이 높이 를 더미 에서 삭제 해 야 한다.위의 조작 을 마 친 후에 기 록 된 윤곽 높이 와 현재 지붕 기록 의 최고 높이 를 비교 하면 이 윤곽 의 높이 가 변화 했다 는 것 을 증명 한다.
위 에 있 는 동작 은 더미 에서 요 소 를 삭제 하고 JAVA 의 Priority Queue 를 사용 하 는 것 입 니 다. 시간 복잡 도 는 O (n) 입 니 다. 여 기 는 TreeMap 이나 TreeSet 로 최적화 할 수 있 습 니 다.

public List getSkyline(int[][] buildings) {
    List res = new ArrayList<>();
    if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
        return res;
    }

    //init height list
    List Coors = new ArrayList<>();
    for (int[] building : buildings) {
        Coors.add(new int[]{building[0], -building[2]});
        Coors.add(new int[]{building[1], building[2]});
    }
    Collections.sort(Coors, new Comparator() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        }
    });

    //init PriorityQueue,  keep the max height until now
    Queue maxHeightHeap = new PriorityQueue<>(new Comparator(){
        public int compare(Integer a, Integer b) {
            return b - a;
        }
    });

    maxHeightHeap.add(0);
    int pre = 0, cur = 0;
    for (int i = 0; i < Coors.size(); i++) {
        int[] Coor = Coors.get(i);
        if (Coor[1] < 0) {
            maxHeightHeap.add(-Coor[1]);
        } else {
            maxHeightHeap.remove(Coor[1]);
        }
        cur = maxHeightHeap.peek();
        if (cur != pre) {
            res.add(new int[]{Coor[0], cur});
            pre = cur;
        }
    }

    return res;
}