【堆 （优先队列) 扫描线】218. 天际线问题

本文涉及知识点

堆 （优先队列) 扫描线

LeetCode218. 天际线问题

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。
每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。
天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

示例 1：

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
示例 2：

输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]

提示：

1 <= buildings.length <= 10⁴
0 <= lefti < righti <= 2³¹ - 1
1 <= heighti <= 2³¹ - 1
buildings 按 lefti 非递减排序

懒删除堆+ 扫描线

通过观察示例，我们可以得出如下结论：
性质一：关键点的横坐标一定是建筑的左右边缘。令建筑的左右边缘的集合是xs。
性质二：xs中除以下元素外，全部是关键点：
$\forall$x,i ,其中 x$\in$xs。 x in $[lefti,righti] x对应的height 小于等于heighti。
性质三：根据性质二，一个x对应多个height，取最大值。xh记录x及对应高度。
性质四：根据性质三，性质二可以简化为 x in $(lefti,righti)
lh 记录左边界及高度。
rh记录有边界及高度。
xh、lh、rh都按x的升序排序。
有序mulset has代替懒删除堆 记录：
lefti < x ,righti > x的高度。 如果高度的最大值小于x对应的高度，则是关键点。

关键点的纵坐标y
$$\{\begin{array}{llc}0& & 不存在lefti小于等于x,righti大于x的建筑\\ 这些建筑的最大高度& & other\end{array}$$
如果两个相邻的关键点高度相同，删除前面的关键点。

代码

核心代码

  class Solution {
  public:
	  vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
		  vector<pair<int, int>> tmp,xh, lh, rh;
		  for (const auto& v : buildings) {
			  lh.emplace_back(make_pair(v[0], v[2]));
			  rh.emplace_back(make_pair(v[1], v[2]));
		  }
		  tmp = lh;
		  tmp.insert(tmp.end(), rh.begin(), rh.end());
		  sort(tmp.begin(), tmp.end());
		  sort(rh.begin(), rh.end());		 
		  for (const auto& [x, h] : tmp) {
			  if (xh.size() && (xh.back().first == x)) {
				  xh.back().second = h;
			  }
			  else {
				  xh.emplace_back(make_pair(x, h));
			  }
		  }
		  multiset<int> has;
		  int il = 0, ir = 0;
		  vector<vector<int>> ret;
		  for (const auto& [x, h] : xh) {			 
			  while ((il < lh.size() )&& (lh[il].first < x)) {
				  has.emplace(lh[il++].second);
			  }
			  while ((ir < rh.size()) && (rh[ir].first <= x)) {
				  has.erase(has.find(rh[ir].second));
				  ir++;
			  }
			  if (has.empty() || (*has.rbegin() < h)) {
				  ret.emplace_back(vector<int>{ x,-1 });
			  }
			  while ((il < lh.size()) && (lh[il].first <= x)) {
				  has.emplace(lh[il++].second);
			  }
			  ret.back()[1] = has.empty()?0: *has.rbegin();	 
		  }		
		  vector < vector<int>> ret2 = { ret[0] };
		  for (int i = 1; i < ret.size(); i++) {
			  if (ret2.back()[1] != ret[i][1]) {
				  ret2.emplace_back(ret[i]);
			  }
		  }
		  return ret2;
	  }
  };

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{	
	vector<vector<int>> buildings;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod00)
		{
			buildings = { {2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8} };
			auto res = Solution().getSkyline(buildings);
			AssertV2(vector<vector<int>>{ {2, 10}, { 3,15 }, { 7,12 }, { 12,0 }, { 15,10 }, { 20,8 }, { 24,0 }}, res);
		}
		TEST_METHOD(TestMethod01)
		{
			buildings = { {0,2,3},{2,5,3} }		;
			auto res = Solution().getSkyline(buildings);
			AssertV2(vector<vector<int>>{ {0, 3}, { 5,0 }}, res);
		}
		
	};
}

简化思路

所有x都是关键点，除非y和前一个x相同。
y = max(所有左边界 <= x，右边界大于x的建筑高度)，所有没有符合的建筑y为0。

class Solution {
public:
	vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
		vector<pair<int, int>> tmp, xh, lh, rh;
		for (const auto& v : buildings) {
			lh.emplace_back(make_pair(v[0], v[2]));
			rh.emplace_back(make_pair(v[1], v[2]));
		}
		tmp = lh;
		tmp.insert(tmp.end(), rh.begin(), rh.end());
		sort(tmp.begin(), tmp.end());
		sort(rh.begin(), rh.end());
		for (const auto& [x, h] : tmp) {
			if (xh.size() && (xh.back().first == x)) {
				xh.back().second = h;
			}
			else {
				xh.emplace_back(make_pair(x, h));
			}
		}
		multiset<int> has;
		int il = 0, ir = 0;
		vector<vector<int>> ret;
		for (const auto& [x, h] : xh) {
			while ((il < lh.size()) && (lh[il].first <= x)) {
				has.emplace(lh[il++].second);
			}
			while ((ir < rh.size()) && (rh[ir].first <= x)) {
				has.erase(has.find(rh[ir].second));
				ir++;
			}
			int y = has.empty() ? 0 : *has.rbegin();
			if (ret.empty() || (ret.back()[1] != y)) {
				ret.emplace_back(vector<int>{x, y});
			}
		}
		return ret;
	}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。