力扣—218.天际线问题 ##扫描线+优先队列

题目： 每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

• lefti 是第 i 座建筑物左边缘的 x 坐标。

• righti 是第 i 座建筑物右边缘的 x 坐标。

• heighti 是第 i 座建筑物的高度。

• 天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
  注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

   当关键点为某建筑的右边缘时，该建筑的高度对关键点的纵坐标是没有贡献的。例如图中横坐标为 77 的关键点，虽然它落在红色建筑的右边缘，但红色建筑对其并纵坐标并没有贡献。因此我们给出「包含该横坐标」的定义：建筑的左边缘小于等于该横坐标，右边缘大于该横坐标（也就是我们不考虑建筑的右边缘）。即对于包含横坐标 x 的建筑 i，有 x∈[left i​	 ,right i​	 )。
   特别地，在部分情况下，「包含该横坐标」的建筑并不存在。例如当图中只有一座建筑时，该建筑的左右边缘均对应一个关键点，当横坐标为其右边缘时，这唯一的建筑对其纵坐标没有贡献。因此该横坐标对应的纵坐标的大小为 0。
  
   一个暴力的算法：O(n) 地枚举建筑的每一个边缘作为关键点的横坐标，过程中我们 O(n) 地检查每一座建筑是否「包含该横坐标」，找到最大高度，即为该关键点的纵坐标。该算法的时间复杂度是 O(n^2)，我们需要进行优化。
  

优化后题解：

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        //建立优先队列，在枚举横坐标时实时更新该队列，优化寻找最大高度的时间，保证队首元素为最大高度
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
        //保存所有的边缘坐标，并排序
        List<Integer> boundaries = new ArrayList<Integer>();
        for (int[] building : buildings) {
            boundaries.add(building[0]);
            boundaries.add(building[1]);
        }
        Collections.sort(boundaries);

        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        int n = buildings.length, idx = 0;
        for (int boundary : boundaries) {
            while (idx < n && buildings[idx][0] <= boundary) {
                pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
                idx++;
            }
            while (!pq.isEmpty() && pq.peek()[0] <= boundary) {
                pq.poll();
            }

            //maxn用来记录最大高度的值
            int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
            if (ret.size() == 0 || maxn != ret.get(ret.size() - 1).get(1)) {
                ret.add(Arrays.asList(boundary, maxn));
            }
        }
        return ret;
    }
}

复杂度分析：

• 时间复杂度：O(nlogn)，其中 nn 为建筑数量。每座建筑至多只需要入队与出队一次，单次时间复杂度为 O(logn)。
• 空间复杂度：O(n)，其中 n 为建筑数量。数组 boundaries 和优先队列的空间占用均为 O(n)。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/the-skyline-problem/solution/tian-ji-xian-wen-ti-by-leetcode-solution-ozse/
来源：力扣（LeetCode）