天际线问题"/>
OJ练习第183题——天际线问题
天际线问题
力扣链接:218. 天际线问题
题目描述
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度,请返回 由这些建筑物形成的 天际线 。
示例
官解思路(扫描线+优先队列)
观察题目我们可以发现,关键点的横坐标总是落在建筑的左右边缘上。这样我们可以只考虑每一座建筑的边缘作为横坐标,这样其对应的纵坐标为「包含该横坐标」的所有建筑的最大高度。
观察示例一可以发现,当关键点为某建筑的右边缘时,该建筑的高度对关键点的纵坐标是没有贡献的。
class Solution {public List<List<Integer>> getSkyline(int[][] buildings) {PriorityQueue<int[]> pq = new PriorityQueue<>((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<>();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();}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;}
}
更多推荐
OJ练习第183题——天际线问题
发布评论