例题

LeetCode 218 The 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. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

• \(left_i\)is the x coordinate of the left edge of the \(i^{th}\) building.
• \(right_i\)is the x coordinate of the right edge of the \(i^{th}\) building.
• \(height_i\) is the height of the\(i^{th}\)building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: 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],...]

Example 1:

Input: buildings =[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]

Output:[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Explanation:

Figure A shows the buildings of the input.

Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

扫描线思路及算法

观察题目我们可以发现，关键点的横坐标总是落在建筑的左右边缘上。这样我们可以只考虑每一座建筑的边缘作为横坐标，这样其对应的纵坐标为「包含该横坐标」的所有建筑的最大高度。

观察示例一可以发现，当关键点为某建筑的右边缘时，该建筑的高度对关键点的纵坐标是没有贡献的。例如图中横坐标为 77 的关键点，虽然它落在红色建筑的右边缘，但红色建筑对其并纵坐标并没有贡献。因此我们给出「包含该横坐标」的定义：建筑的左边缘小于等于该横坐标，右边缘大于该横坐标（也就是我们不考虑建筑的右边缘）。即对于包含横坐标 x 的建筑 \(i\)，有\(x∈[left_i,right_i\))。

特别地，在部分情况下，「包含该横坐标」的建筑并不存在。例如当图中只有一座建筑时，该建筑的左右边缘均对应一个关键点，当横坐标为其右边缘时，这唯一的建筑对其纵坐标没有贡献。因此该横坐标对应的纵坐标的大小为 0。

这样我们可以想到一个暴力的算法：\(O(n)\)地枚举建筑的每一个边缘作为关键点的横坐标，过程中我们 \(O(n)\)地检查每一座建筑是否「包含该横坐标」，找到最大高度，即为该关键点的纵坐标。该算法的时间复杂度是 \(O(n^2)\)，我们需要进行优化。

我们可以用优先队列来优化寻找最大高度的时间，在我们从左到右枚举横坐标的过程中，实时地更新该优先队列即可。这样无论何时，优先队列的队首元素即为最大高度。为了维护优先队列，我们需要使用「延迟删除」的技巧，即我们无需每次横坐标改变就立刻将优先队列中所有不符合条件的元素都删除，而只需要保证优先队列的队首元素「包含该横坐标」即可。

具体地，为了按顺序枚举横坐标，我们用数组 \(\textit{boundaries}\) 保存所有的边缘，排序后遍历该数组即可。过程中，我们首先将「包含该横坐标」的建筑加入到优先队列中，然后不断检查优先队列的队首元素是否「包含该横坐标」，如果不「包含该横坐标」，我们就将该队首元素弹出队列，直到队空或队首元素「包含该横坐标」即可。最后我们用变量 \(\textit{maxn}\)记录最大高度（即纵坐标的值），当优先队列为空时，\(\textit{maxn}=0\)，否则\(\textit{maxn}\)即为队首元素。最后我们还需要再做一步检查：如果当前关键点的纵坐标大小与前一个关键点的纵坐标大小相同，则说明当前关键点无效，我们跳过该关键点即可。

这里需要强调的是，如果紧接着的俩纵坐标一样的楼房的话，skyline 里算作一个，并没有被刷新！！！！所以要跳过当前关键点的值\(maxn\)与前一个关键点的值res.back()相同的元素。

在实际代码中，我们可以进行一个优化。因为每一座建筑的左边缘信息只被用作加入优先队列时的依据，当其加入优先队列后，我们只需要用到其高度信息（对最大高度有贡献）以及其右边缘信息（弹出优先队列的依据），因此只需要在优先队列中保存这两个元素即可。

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        auto cmp = [](pair<int,int> &a,pair<int,int> &b)->bool{return a.second<b.second;};
        priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> queue(cmp);
        vector<vector<int> > res;

        vector<int> scan;
        //store all scannning lines,sorted by their x-coordinate
        for(vector<int> &building:buildings){
            scan.emplace_back(building[0]);
            scan.emplace_back(building[1]);
        }
        //all canning line should be in order
        sort(scan.begin(),scan.end());
        //scan
        int b_index = 0, n = buildings.size();
        for(int &line:scan){
            //input by left edge
            while(b_index<n&&buildings[b_index][0]<=line){
                queue.emplace(buildings[b_index][1],buildings[b_index][2]);
                b_index++;
            }
            //delay delete, delete onlny when use it
            while(!queue.empty()&&queue.top().first<=line){
                queue.pop();
            }

            int maxn = queue.empty() ? 0 : queue.top().second;
            //current max number != the latest one, we should add it to results
            if(res.size()==0||maxn!=res.back()[1]){
                res.push_back({line,maxn});
            }

        }
        return res;

    }
};

线段树思路及算法

区间操作+单点查询+离散化，复杂度 O(nlogn)。

这个线段树的写法确实比较特殊，是由两个树状数组拼起来构成的。

class SegmentTree {
public:
    struct node {
        int tag;
        int val;
    };

private:
    using node_ptr = node*;
    node_ptr prefix, suffix; //左右子树指针

    inline static int lowbit(int x) {//最低比特位
        return x & -x;
    }

public:
    SegmentTree(size_t n) : prefix(new node[2 * n]), suffix(prefix + n) {}

    inline size_t size() const {
        return suffix - prefix;
    }

    inline void pushup(int p, int d, size_t s) { 
        const int n = size();
        if (s == 0) return;
        int i = p + lowbit(s);
        int j = p - lowbit(s);
        for (;i <= n;i += lowbit(i))
            prefix[i].val = max(prefix[i].val, d);
        for (i -= lowbit(i);j > i;j -= lowbit(j))
            suffix[j].val = max(suffix[j].val, d);
    }

    inline void update(int l, int r, int d) {//左端点，右端点，数值
        const int n = size();
        int i = l, j = r;
        if (l > 0) 
          for (;i + lowbit(i) <= r;i += lowbit(i)) {
            suffix[i].val = max(suffix[i].val, d);
            suffix[i].tag = max(suffix[i].tag, d);
        	}
        for (;j > i;j -= lowbit(j)) {
            prefix[j].val = max(prefix[j].val, d);
            prefix[j].tag = max(prefix[j].tag, d);
        }
        pushup(l, d, i - l);
        pushup(r, d, r - i);
    }

    inline int query(int p) const {
        const int n = size();
        int ans = 0;
        for (int i = p + 1;i <= n;i += lowbit(i))
            ans = max(ans, prefix[i].tag);
        for (int i = p;i > 0;i -= lowbit(i))
            ans = max(ans, suffix[i].tag);
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<int> order;
        for (const auto& e : buildings) {
            order.push_back(e[0]);
            order.push_back(e[1]);
        }
        auto first = order.begin();
        auto last = order.end();
        sort(first, last);//
        /*unique（C++）函数的功能是元素去重。即”删除”序列中所有相邻的重复元素(只保留一个)。
          此处的删除，并不是真的删除，就是把重复元素的位置让不重复元素使用。返回值是去重之后的尾地址（是地址！！）
          由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。*/
        /*erase（first，last）;删除从first到last之间的字符，（first和last都是迭代器）*/
        last = order.erase(unique(first, last), last);
        const int n = order.size();
        SegmentTree tree(n);
        for (const auto& e : buildings) {
            const int l = lower_bound(first, last, e[0]) - first;
            const int r = lower_bound(first, last, e[1]) - first;
            tree.update(l, r, e[2]);
        }
        int prev = 0;
        vector<vector<int>> ans;
        for (int i = 0;i < n;++i) {
            const int cur = tree.query(i);
            if (cur != prev) ans.push_back({order[i], prev = cur});
        }
        return ans;
    }
};