城市天际线问题 | 第一部分

给定二维城市中的 n 栋矩形建筑，计算出这些建筑的天际线，并消除被遮挡的线条。我们的主要任务是从侧面观察这些建筑，并移除所有不可见的部分。所有建筑共用同一个底部，且每栋建筑都由一个三元组 来表示：

• ‘left‘：建筑左侧（或墙）的 x 坐标。
• ‘right‘：建筑右侧的 x 坐标。
• ‘ht‘：建筑的高度。

天际线是一系列矩形条的集合。每一个矩形条表示为一对 ，其中 left 是该条左侧的 x 坐标，ht 是该条的高度。

示例：

> 输入： build[][] = [[1, 5, 11], [2, 7, 6], [3, 9, 13], [12, 16, 7], [14, 25, 3], [19, 22, 18], [23, 29, 13], [24, 28, 4]]

> 输出： [[1, 11], [3, 13], [9, 0], [12, 7], [16, 3], [19, 18], [22, 3], [23, 13], [29, 0]]

> 解释： 天际线是基于关键点（图中用“绿色”点表示）形成的，这些关键点消除了被遮挡的墙体。请注意，第二栋建筑 (2, 7, 6) 没有端点被考虑在内，因为它被完全重叠了。此外，y 坐标发生变化的点也被考虑在内。（注意，第三栋建筑 (3, 9, 13) 的右上角点没有被考虑，因为它具有相同的 y 坐标。）

>

> !sl1城市天际线问题

> 输入：build[ ][ ] = [[1, 5, 11]]

> 输出：[[1, 11], [5, 0]]

解法的通用背景

让我们通过第一个示例 [[1, 5, 11], [2, 7, 6], [3, 9, 13], [12, 16, 7], [14, 25, 3], [19, 22, 18], [23, 29, 13], [24, 28, 4]] 来更好地理解这个问题。

有一点很明显，我们要从左到右构建天际线。现在我们知道点 [1, 11] 肯定会出现在输出中，因为它是最左边的点。

如果我们看第一栋建筑的右点 INLINECODEe4a157a2，会发现这个点不能被计入，因为有一栋更高的建筑（我们输入数组中的第三栋建筑 INLINECODE8f7de139）。所以我们忽略这个右点。

现在我们来看第二栋建筑，它的左边和右边都被覆盖了。左边被第一栋建筑覆盖，右边被第三栋建筑覆盖，因为它的高度比它两边的邻居都小。所以我们完全忽略第二栋建筑。

我们用同样的方式处理所有剩余的建筑。

朴素扫描线算法 – O(n^2) 时间复杂度和 O(n) 空间复杂度

• 将所有建筑的所有角点 x 坐标放入一个数组，比如 points[]。因为每栋建筑都有左右两个坐标，所以这个数组中主要会有 2n 个点。
• 对 points[] 进行排序，以模拟从左到右的扫描线。
• 现在遍历排序后的 points[]，对于每一个 x 点，检查哪栋建筑在该点具有最大高度，并且如果最大高度与之前添加到天际线的高度不同，则将此最大高度添加到天际线中。

C++

#include 
#include 
#include 
using namespace std;

vector<pair> getSkyline(vector<vector>& build) {
    vector points;

    // Collect all left and right x-coordinates
    // of buildings
    for (auto& b : build) {
        points.push_back(b[0]);
        points.push_back(b[1]);
    }

    // Sort all critical points
    sort(points.begin(), points.end());

    vector<pair> res;
    int prev = 0;

    // Traverse through each point to
    // determine skyline height
    for (int x : points) {
        int maxH = 0;

        // Check which buildings cover the 
        // current x and get the max height
        for (auto& b : build) {
            int l = b[0], r = b[1], h = b[2];
            if (l <= x && x < r) {
                maxH = max(maxH, h);
            }
        }

        // Add to result if height has changed
        if (res.empty() || maxH != prev) {
            res.push_back({x, maxH});
            prev = maxH;
        }
    }

    return res;
}

int main() {
    vector<vector> build = {
        {2, 9, 10},
        {3, 6, 15},
        {5, 12, 12}
    };

    vector<pair> skyline = getSkyline(build);

    for (auto& p : skyline) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }

    cout << endl;
    return 0;
}

`

Java

import java.util.*;

class Solution {
    public List getSkyline(int[][] build) {
        List points = new ArrayList();

        // Collect all left and right x-coordinates
        // of buildings
        for (int[] b : build) {
            points.add(b[0]);
            points.add(b[1]);
        }

        // Sort all critical points
        Collections.sort(points);

        List res = new ArrayList();
        int prev = 0;

        // Traverse through each point to
        // determine skyline height
        for (int x