[抄题]:
水平面上有 N 座大楼,每座大楼都是矩阵的形状,可以用一个三元组表示 (start, end, height)
,分别代表其在x轴上的起点,终点和高度。大楼之间从远处看可能会重叠,求出 N 座大楼的外轮廓线。
外轮廓线的表示方法为若干三元组,每个三元组包含三个数字 (start, end, height),代表这段轮廓的起始位置,终止位置和高度。
[暴力解法]:
时间分析:
空间分析:
[思维问题]:
抽象不出来特点
[一句话思路]:
起点影响中间,终点不影响中间,中间用pq比较
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- for(int[] b:buildings)可以同时满足新建b[]、循环的要求,没用过
- h[1] > 0代表末尾高度,不再进行中间最大点的循环,要从heap中移除。没理解
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
本质上还是根据特点选取数据结构:要最大值就要用pq
[复杂度]:Time complexity: O(nlgn) Space complexity: O(n)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
- 自制comparator,a - b 构造的是最小堆,参数中应该反过来,才是最大堆。忘了。
- new int[]{b[0], -b[2]}, 括号还是要写的,因为毕竟是数组类型,不是整数类型
[关键模板化代码]:
Collections.sort(height, (a,b) -> { if (a[0] != b[0]) return a[0] - b[0]; return a[1] - b[1]; });
public int compareTo(Node other) { Node a =(Node)other; if (this.val == a.val) { return this.id - a.id; } return this.val - a.val; }
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
[代码风格] :
class Solution { public List<int[]> getSkyline(int[][] buildings) { //corner case List<int[]> result = new ArrayList<int[]>(); List<int[]> height = new ArrayList<int[]>(); //put all buildings into heights for (int[] b : buildings) { height.add(new int[]{b[0], -b[2]}); height.add(new int[]{b[1], b[2]}); } Collections.sort(height, (a,b) -> { if (a[0] != b[0]) return a[0] - b[0]; return a[1] - b[1]; }); PriorityQueue<Integer> q = new PriorityQueue<Integer>((a,b) -> (b - a)); q.offer(0);//add first int prev = 0; //get all starts & ends into q for (int[] h : height) { if (h[1] < 0) { q.offer(- h[1]); }else { q.remove(h[1]); } //add the maximum in the middle, compare int curt = q.peek(); if (prev != curt) { result.add(new int[]{h[0], curt}); prev= curt; } } return result; } }