天际线问题

天际线问题(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 are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ 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], ...]

解题思路

用中文简单描述一下：

在一个二维平面上分布着许多矩形的建筑物，你需要将它们的轮廓线用特定的坐标表示出来

规定：输出的轮廓线中每一个矩形的左上角坐标，而末尾坐标一定为(x, 0)

初一看，要求的点一定在轮廓线的交叉点或者转折点上，而这些点又一定伴随着某个矩阵的开始或者结束（但并不是每一个开始或者结束点都会产生这些点），因此一个初步的思路是将这些点按一定的顺序排列起来，然后在遍历这些点的过程中，根据当前建筑物的高度决定是否输出某个点。

答案中的点一定在图中的点产生（把高度为0也看成一个矩形），而只有绿色的点才是我们需要输出的。

可以进一步思考，因为所求的是轮廓线上的点，因此一定和最大高度有关系。假设我们在从左往右检查的过程中，建筑物在依次地生成和销毁，一般情况下（先不考虑重合情况），当一个建筑物开始生成时，如果它的高度比最大高度要小，则不会产生轮廓线，否则为需要输出的点；而当某个建筑物开始消失时，如果最大高度没有改变，则同样不会影响轮廓线，而如果最大高度减小了，说明会和 次大高度 产生一个交叉点，这个点也是需要输出的（两种需要输出情况分别对应上图中第一二个绿色的点）。通过这种思想，我们就需要时刻能够取出和删除最大高度，因此采用优先队列或者二叉平衡树的结构是很理想的（一般使用平衡树，因为需要删除结构中的非最大值）。

然而，仍然有三种情况需要额外考虑：

1. 两建筑物同时生成

   即起始点的横坐标相同，这时需要先让较高的建筑物生成，以避免输出较矮的那个高度（可以反证法验证一下），否则按逻辑顺序生成。

2. 两建筑物同时摧毁

   即结束点的横坐标相同，这时需要先让较矮的建筑物摧毁，以避免输出较矮的那个高度，否则按逻辑顺序摧毁。

3. 前一个摧毁的同时，后一个立即生成

   即结束点和起始点的横坐标相同，这时需要先生成建筑物；如果两建筑物刚好高度相同，则不能输出轮廓点。

讨论完所有情况后，就可以按照规则先将这些点排列起来了。我们用这样一种方式来表示不同意义的点：
$$
[x, height, start _{or} end]
$$
其中x表示点的横坐标，height表示高度，最后一个参数表示该点是起始点还是结束点。

别担心，尽管这种方式只能表示起始和结束点的坐标，但是结合平衡树后就能够产生交叉点了（当前横坐标+平衡树中存储的最大高度）。

先根据题目给出的建筑物坐标以上述方式依次写出各点：

[2, 10, s]

[9, 10, e]

[3, 15, s]

[7, 15, e]

[5, 12, s]

[12, 12, e]

[15, 10, s]

[20, 10, e]

[19, 8, s]

[24, 8, e]

但是，这种顺序是无法满足要求的，根据前面的思想，我们需要制定如下规则：

1. 横坐标小的放前面
2. 横坐标相同
   1. 同为s, 先放高的
   2. 同为e, 先放矮的
   3. 一s一e， 先放s

经过上述规则后排序如下：

[2, 10, s]

[3, 15, s]

[5, 12, s]

[7, 15, e]

[9, 10 , e]

[12, 12, e]

[15, 10, s]

[19, 8, s]

[20, 10, e]

[24, 8, e]

接下来就可以正式处理这些点了：

需要的结构体：平衡树，初始值为0（假定也是一个矩形）；数组，存放和排序上述点。

对于某个具体点：

​ 如果是起始点，将高度插入树中（相当于生成建筑物），并且如果高度大于最大高度，输出这个点。

​ 如果是结束点，将该高度从树中移除（相当于销毁建筑物），并且如果移除的高度同时是最大高度，则输出该点的横坐标和新的最大高度（即交叉点），但一种情况除外，即两建筑物一生成一摧毁并且高度恰好相同时不能输出为轮廓点！

以下是使用了c++ map 结构的代码，具体map存储高度的方式见代码：

//BuildingPoint,存储是否为起始点，该点的横坐标和该点的高度
struct BuildingPoint{
    bool isStart;
    int x;
    int height;
    BuildingPoint(bool flag, int index, int h){
        isStart = flag;
        x = index;
        height = h;
    }
    bool operator<(const BuildingPoint& a)const{
        if(this->x < a.x){
            return true;
        } else if(this->x > a.x){
            return false;
        } else {
            //如果横坐标相同
            //同为s,先放高的
            //同为e,先放矮的
            //一s一e,先放s
            if(this->isStart && a.isStart){
                if(this->height >= a.height)return true;
                else return false;
            } else if(!this->isStart && !a.isStart){
                if(this->height <= a.height)return true;
                else return false;
            } else {
                if(this->isStart)return true;
                else return false;
            }
        }
    }
};

vector<vector<int>> skyLine(vector<vector<int>>& buildings){
    //用来存放高度的平衡树,键值分别为高度和出现的次数
    map<int, int> heightCounts;
    //当前的最大高度
    int maxHeight = 0;
    //当前高度
    int currentHeight;
    //存放buildPoint的数组
    vector<BuildingPoint> BuildingPoints;
    //存放结果的数组
    vector<vector<int>> ans;

    //初始化
    //初始化heightCounts
    heightCounts[0] = 1;

    //先把所有buildings中的数据放入数组中
    for(auto it = buildings.begin(); it != buildings.end(); it++){
        int startIndex = it->at(0);
        int endIndex = it->at(1);
        int height = it->at(2);
        BuildingPoints.push_back(BuildingPoint(true, startIndex, height));
        BuildingPoints.push_back(BuildingPoint(false, endIndex, height));
    }
    //对该数组进行排序
    sort(BuildingPoints.begin(), BuildingPoints.end());

    //循环处理
    //对于某个具体点：
    //如果是起始点，将高度插入树中，并且如果高度大于最大高度，输出这个点。
    //如果是结束点，将该高度从树中移除，并且如果移除的高度同时是最大高度，则输出该点的横坐标和新的最大高度（即交叉点）。
    for(auto it = BuildingPoints.begin(); it != BuildingPoints.end(); it++){
        if(it->isStart){
            //如果是起点，放入heightCounts中
            if(heightCounts.count(it->height) <= 0){
                heightCounts[it->height] = 1;
            } else {
                heightCounts[it->height]++;
            }
            if(it->height > maxHeight){
                ans.push_back(vector<int>({it->x, it->height}));
                maxHeight = it->height;
            }
        } else {
            //弹出这个结束坐标的高度
            currentHeight = it->height;
            if(heightCounts[currentHeight] == 1){
                heightCounts.erase(currentHeight);
            } else {
                heightCounts[currentHeight]--;
            }

            //如果同时是最大值，则更新最大高度，输出当前坐标值和新的最大高度
            if(currentHeight == maxHeight){
                maxHeight = heightCounts.rbegin()->first;
                if(maxHeight != currentHeight){//特殊情况：高度相等时不能作为轮廓点
                    ans.push_back(vector<int>({it->x, maxHeight}));
                }
            }
        }
    }
    return ans;
}

核心思想

利用优先队列或者平衡树结构来存储建筑物，以实时根据最大高度输出结果。

参考解法链接：

Skyline Problem