LeetCode 218. 天际线问题（multiset优先队列）*

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。 现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。

在这里插入图片描述

在这里插入图片描述

每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标，Hi 是其高度。 可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。 您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。

例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。

输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。 关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。 此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。

说明: 任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。 输入列表已经按左 x 坐标 Li 进行升序排列。 输出列表必须按 x 位排序。 输出天际线中不得有连续的相同高度的水平线。 例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案； 三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/the-skyline-problem 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 参考题解区Allen大佬
• 把建筑物左右顶点分开计算，左顶点高度用负数区分
• 把所有顶点插入multiset，开辟另一个高度h的multiset，含初始元素 0
• 遍历所有的顶点，是左顶点则插入该点的 hi，右顶点从 h 中删除 hi
• 读取最大的hi，如果跟上次的不一样，视为拐点，写入答案

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    	vector<vector<int>> ans;
    	if(buildings.size() == 0) return ans;
    	multiset<vector<int>> corner;
    	multiset<int> h;
    	h.insert(0);//有空隙的时候方便处理
    	//把建筑物分为上面左右两个顶点
    	for(auto& bd : buildings)
    	{
    		corner.insert({bd[0], -bd[2]});//左边高度取负号区分
    		corner.insert({bd[1], bd[2]});
    	}
    	//multiset自动按第一个元素排序，相同按第二个
    	vector<int> prev(2,0);//前一个拐角
    	for(auto& cn : corner)
    	{
    		if(cn[1] < 0)//左端点,插入
    			h.insert(-cn[1]);
    		else
    			h.erase(h.find(cn[1]));//右端点删除
    		int maxh = *h.rbegin();
    		if(maxh != prev[1])//高度不相等,遇到拐角
    		{
    			prev[0] = cn[0];
    			prev[1] = maxh;
    			ans.push_back(prev);
    		}
    	}
    	return ans;
    }
};

128 ms 16.4 MB