The Skyline Problem解题心得

原图链接：https://leetcode.com/problems/the-skyline-problem/description/

题目复述

• 如下图所示，已知多个矩形建筑物的左右边界位置以及高度（建筑物都是贴地的）[Li, Ri, Hi] ；由此可见多个矩形建筑物在二维的平面上存在重叠的可能，在这个题目里我们需要求得重叠后的建筑轮廓
• 为了表示重叠后的建筑的轮廓的结果，在这里我们只需要存储轮廓每个横向线段的最左边的点即可（如下图B的轮廓，红色的点即为储存点），最后还需要取得轮廓的最右边的结束点，即一个形式为(xn,0)的点，表示轮廓结束
  

解题思路

• 一脸懵逼的我：在碰到这关于图像类型的题的开始我是无从下手的，我考虑到的方法是挨个向已有的轮廓里加入新的建筑，但是我发现自己分了很多类情况讨论，把问题复杂化了
• 影子叠加算法：通过网上提供的解题思路，和我的进一步分析。发现合并两个轮廓序列的规律方法；这里为了纪念并且使自己更容易记住这个小小的算法，我将它取名为“影子叠加算法”
  
  • 影子叠加的规律：我们可以吧skyline看作是一个影子，对于两个影子的叠加我们可以发现下面的规律
    
    • 在同一竖线上的影子我们实际只能看到竖线上较高的那个影子的轮廓，因为矮的那个影子会被高的影子屏蔽掉
  • 回到skyline里看规律，我们可以对重叠的两个skyline每个坐标点进行观察，看对于当前xi轮廓边界高度的取值也是满足“影子叠加规律”的，取当前两个轮廓的最高高度
  • 影子叠加算法具体实现
    
    • 设两个已经按x坐标排序的skyline坐标的数组的当前高度h1和h2，初始化为0
    • 每次比较两个数组头的坐标的x值（比如pos1，pos2）
      
      • 假设 pos1.x<pos2.x
        
        • 在对应的数组skyline1头弹出pos1
        • 同时更新pos1对应skyline1高度值h1
        • h1=pos1.y
        • 将pos1插入合并后的数组newskyline前，比较h1，h2，取其中较大的数更新为pos1的新的高度，将pos1插入数组，（注意：插入前要消重，防止插入连续y值相等的坐标）
        • newskyline.push_back(pair<int, inr>(pos1.x, max(h1, h2)));
      • 当pos1.x==pos2.x
        
        • 同时弹出skyline1，skyline2的头元素pos1， pos2
        • 更新h1， h2
        • 再一次插入更新高度为max(h1, h2)新的坐标值到新合并后的数组中（注意：插入前要消重，防止插入连续y值相等的坐标）
• 分治优化算法：
  
  • 在我们获得skyline合并算法的核心后我们可以完成对一个一个建筑物的加入一个累积skyline，由此可见要遍历所有建筑，而且每个建筑要和累积的skyline比较插入。时间复杂度为O(n2)
  • 于是我们可以采用分治的方法来优化算法的时间复杂度，将已有的建筑物分为两个部分，对子部分递归分块，最终分为只有两个或一个建筑物就向归并向上，类似归并排序，由于分治递推式T(n)=2T(n/2)+O(n)，所以有O(nlogn)的时间复杂度
  • 在这里我没有使用递归调用函数的方法，而是使用一个队列，push入所有skyline形式的建筑物，再依次取出两个归并后插入队列尾。实现之间从二叉树的底部向上归并的思路
• 我的代码地址：
  

https://github.com/zhanzongyuan/leetcode/blob/master/218_The%20Skyline%20Problem.cpp