LeetCode 题解（96）: The Skyline Problem

2024-05-28 09:18
文章标签 leetcode 题解 problem 96 skyline

本文主要是介绍LeetCode 题解（96）: The Skyline Problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you aregiven the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program tooutput the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour

The geometric information of each building is represented by a triplet of integers[Li, Ri, Hi], whereLi and Ri are the x coordinates of the left and right edge of the ith building, respectively, andHi is its height. It is guaranteed that0 ≤ Li, Ri ≤ INT_MAX,0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of[ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline.A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance,[...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such:[...[2 3], [4 5], [12 7], ...]
题解：

解法一：总体思想是Divide and Conquer，但是Conquer的时候需要特殊处理左边重叠的情况。Merge的基本思路是设两个变量h1 = 0, h2 = 0，以及maxH用于记录上次的高度。取两个序列中x小的，相应的改变h1或h2的值。同时merge后的新元素为（x.min, max(h1, h2)），并且只有当max(h1,h2) != maxH的时候才更新，这样可以防止添加进高度一样的元素。然后令maxH = max(h1, h2)保存当次的高度值，用于下次更新时的比较。

C++版：

class Solution {
public:vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {vector<pair<int, int>> results;if (buildings.size() == 0)return results;if (buildings.size() == 1) {results.push_back(pair<int, int>(buildings[0][0], buildings[0][2]));results.push_back(pair<int, int>(buildings[0][1], 0));return results;}vector<pair<int, int>> left = divide(0, (buildings.size() - 1) / 2, buildings);vector<pair<int, int>> right = divide((buildings.size() - 1) / 2 + 1, buildings.size() - 1, buildings);results = conquer(left, right);return results;}vector<pair<int, int>> divide(int start, int end, vector<vector<int>>& buildings) {if (start == end) {vector<pair<int, int>> result;result.push_back(pair<int, int>(buildings[start][0], buildings[start][2]));result.push_back(pair<int, int>(buildings[start][1], 0));return result;}int mid = (end + start) / 2;vector<pair<int, int>> left = divide(start, mid, buildings);vector<pair<int, int>> right = divide(mid + 1, end, buildings);vector<pair<int, int>> result = conquer(left, right);return result;}vector<pair<int, int>> conquer(vector<pair<int, int>>& left, vector<pair<int, int>>& right) {vector<pair<int, int>> result;int i = 0, j = 0, h1 = 0, h2 = 0;int maxH = max(h1, h2);while (i != left.size() && j != right.size()) {if (left[i].first < right[j].first) {h1 = left[i].second;if (maxH != max(h1, h2))result.push_back(pair<int, int>(left[i].first, max(h1, h2)));maxH = max(h1, h2);i++;}else if (left[i].first > right[j].first) {h2 = right[j].second;if (maxH != max(h1, h2))result.push_back(pair<int, int>(right[j].first, max(h1, h2)));maxH = max(h1, h2);j++;} else {if(left[i].second >= right[j].second) {h1 = left[i].second;h2 = right[j].second;if(maxH != max(h1, h2))result.push_back(pair<int, int>(left[i].first, left[i].second));maxH = max(h1, h2);i++;j++;} else {h1 = left[i].second;h2 = right[j].second;if(maxH != max(h1, h2))result.push_back(pair<int, int>(right[j].first, right[j].second));maxH = max(h1, h2);i++;j++;			        }}}while (j < right.size()) {result.push_back(right[j]);j++;}while (i != left.size()) {result.push_back(left[i]);i++;}return result;}};
注意当 
left[i].first == right[j].first
时，需要同时更新h1, h2, 并计算maxH，同时i,j都进一位。

解法二：

使用multiset,可以保存有序的重复值。

class Solution {
public:vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {vector<pair<int, int>> results;if (buildings.size() == 0)return results;vector<pair<int, int>> corners;for (auto i : buildings) {corners.push_back(pair<int, int>(i[0], -i[2]));corners.push_back(pair<int, int>(i[1], i[2]));}sort(corners.begin(), corners.end());multiset<int> height;int lastHeight = 0;height.insert(0);for (int i = 0; i < corners.size(); i++) {int h = corners[i].second;if (h < 0) {height.insert(-h);}else {height.erase(height.find(h));}int curHeight = *height.rbegin();if (curHeight != lastHeight)results.push_back(pair<int, int>(corners[i].first, curHeight));lastHeight = curHeight;}return results;}
};


Java版：

解法一：

public class Solution {public List<int[]> getSkyline(int[][] buildings) {List<int[]> results = new ArrayList<>();if(buildings.length == 0)return results;if(buildings.length == 1) {results.add(new int[]{buildings[0][0], buildings[0][2]});results.add(new int[]{buildings[0][1], 0});return results;}int mid = (buildings.length - 1) / 2;List<int[]> left = divide(0, mid, buildings);List<int[]> right = divide(mid + 1, buildings.length - 1, buildings);results = conquer(left, right);return results;}List<int[]> divide(int start, int end, int[][] buildings) {List<int[]> result = new ArrayList<>();if(start == end) {result.add(new int[]{buildings[start][0], buildings[start][2]});result.add(new int[]{buildings[start][1], 0});return result;}int mid = (start + end) / 2;List<int[]> left = divide(start, mid, buildings);List<int[]> right = divide(mid + 1, end, buildings);result = conquer(left, right);return result;}List<int[]> conquer(List<int[]> left, List<int[]> right) {List<int[]> result = new ArrayList<>();int i = 0, j = 0;int h1 = 0, h2 = 0;int maxH = 0;while(i < left.size() && j < right.size()) {if(left.get(i)[0] < right.get(j)[0]) {h1 = left.get(i)[1];if(maxH != Math.max(h1, h2)) {result.add(new int[]{left.get(i)[0], Math.max(h1, h2)});}maxH = Math.max(h1, h2);i++;} else if(left.get(i)[0] > right.get(j)[0]) {h2 = right.get(j)[1];if(maxH != Math.max(h1, h2)) {result.add(new int[]{right.get(j)[0], Math.max(h1, h2)});}maxH = Math.max(h1, h2);j++;} else {h1 = left.get(i)[1];h2 = right.get(j)[1];if(maxH != Math.max(h1, h2))result.add(new int[]{left.get(i)[0], Math.max(h1, h2)});maxH = Math.max(h1, h2);i++;j++;}}while(i < left.size()) {result.add(new int[]{left.get(i)[0], left.get(i)[1]});i++;}while(j < right.size()) {result.add(new int[]{right.get(j)[0], right.get(j)[1]});j++;}return result;}
}

解法二： 

public class Solution {public List<int[]> getSkyline(int[][] buildings) {List<int[]> results = new ArrayList<>();if(buildings.length == 0)return results;PriorityQueue<Integer> height = new PriorityQueue<>(1, new Comparator<Integer>(){public int compare(Integer a, Integer b) {return b - a;}});height.add(0);List<int[]> corners = new ArrayList<>();for(int[] a: buildings) {corners.add(new int[]{a[0], -a[2]});corners.add(new int[]{a[1], a[2]});}int lastHeight = 0;Collections.sort(corners, new Comparator<int[]>(){public int compare(int[] a, int[] b) {if(a[0] != b [0]) {return a[0] - b[0];} else {return a[1] - b[1];}}});for(int i = 0; i < corners.size(); i++) {int h = corners.get(i)[1];if(h < 0) {height.add(-h);} else {height.remove(h);}if(height.peek() != lastHeight) {results.add(new int[]{corners.get(i)[0], height.peek()});}lastHeight = height.peek();}return results;}
}

Python版：

解法一：

class Solution:# @param {integer[][]} buildings# @return {integer[][]}def getSkyline(self, buildings):result = []if len(buildings) == 0:return resultif len(buildings) == 1:result.append([buildings[0][0], buildings[0][2]])result.append([buildings[0][1], 0])return resultmid = (len(buildings) - 1) / 2left = self.divide(0, mid, buildings)right = self.divide(mid + 1, len(buildings)-1, buildings)result = self.conquer(left, right)return resultdef divide(self, start, end, buildings):result = []if start == end:result.append([buildings[start][0], buildings[start][2]])result.append([buildings[start][1], 0])return resultmid = (start + end) / 2left = self.divide(start, mid, buildings)right = self.divide(mid+1, end, buildings)result = self.conquer(left, right)return resultdef conquer(self, left, right):result = []i, j, h1, h2, maxH = 0, 0, 0, 0, 0while i < len(left) and j < len(right):if left[i][0] < right[j][0]:h1 = left[i][1]if maxH != max(h1, h2):result.append([left[i][0], max(h1, h2)])maxH = max(h1, h2)i += 1elif left[i][0] > right[j][0]:h2 = right[j][1]if maxH != max(h1, h2):result.append([right[j][0], max(h1, h2)])maxH = max(h1, h2)j += 1else:h1 = left[i][1]h2 = right[j][1]if maxH != max(h1, h2):result.append([right[j][0], max(h1, h2)])maxH = max(h1, h2)i += 1j += 1while i < len(left):result.append(left[i])i += 1while j < len(right):result.append(right[j])j += 1return result

解法二：

python没有max-heap的实现，这里就不用此方法做了。

这篇关于LeetCode 题解（96）: The Skyline Problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1010152。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）

uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k，? 处可以填 + 也可以填 - ，问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明，令 S（n） = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n，搜出当 S（n） >=
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2