O(n^2) solution: Sweep
public List<List<Integer>> getSkyline(int[][] buildings) { TreeSet<Integer> edgeSet = new TreeSet<>(); for(int[] building : buildings){ edgeSet.add(building[0]); edgeSet.add(building[1]); } List<Integer> positions = new ArrayList<>(edgeSet); Collections.sort(positions); List<List<Integer>> res = new ArrayList<>(); int maxHeight, left, right, height; for(int position : positions){ maxHeight = 0; for(int[] building: buildings){ left = building[0]; right = building[1]; height = building[2]; if(left<=position && position < right){ maxHeight = Math.max(maxHeight, height); } } if(res.isEmpty() || res.get(res.size()-1).get(1) != maxHeight){ res.add(Arrays.asList(position, maxHeight)); } } return res; }
O(nlogn) solution: sweep + PQ/BST
class Solution { public List<int[]> getSkyline(int[][] buildings) { List<int[]> res = new ArrayList<>(); List<int[]> height = new ArrayList<>(); for (int[] building : buildings) { // start point has negative height value height.add(new int[]{building[0], -building[2]}); // end point has normal height value height.add(new int[]{building[1], building[2]}); } Collections.sort(height, new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { if (a[0] == b[0]) { return a[1] - b[1]; } else { return a[0] - b[0]; } } }); // Use a maxHeap to store possible heights // But priority queue does not support remove in lgn time // treemap support add, remove, get max in lgn time, so use treemap here // key: height, value: number of this height TreeMap<Integer, Integer> pq = new TreeMap<>(); pq.put(0, 1); // Before starting, the previous max height is 0; int prev = 0; // visit all points in order for (int[] h : height) { // a start point, add height if (h[1] < 0) { pq.put(-h[1], pq.getOrDefault(-h[1], 0) + 1); } else { // a end point, remove height if (pq.get(h[1]) > 1) { pq.put(h[1], pq.get(h[1]) - 1); } else { pq.remove(h[1]); } } int cur = pq.lastKey(); // compare current max height with previous max height, update result and // previous max height if necessary if (cur != prev) { res.add(new int[]{h[0], cur}); prev = cur; } } return res; } }
https://www.youtube.com/watch?v=GSBLe8cKu0s
https://leetcode.com/problems/the-skyline-problem/discuss/61193/Short-Java-solution
原文地址:http://www.cnblogs.com/jdflyfly/p/16849728.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性