LeetCode

Leetcode 218. The Skyline Problem 题解

查阅更多的题解,请点击
GitHub传送门

Problem

218. The Skyline Problem

Solution

Divide and Conquer, O(nlogn) time

按照一般套路(参考算法笔记(一)概述),观察问题是否可以reduce,最直观的reduce方法是增量式:
* 先求解问题规模n=1的结果
* 再加入一个元素,求解n=2的结果
* ……

从问题规模n-1到问题规模n,只需要处理第n个元素和问题规模n-1时结果的重叠部分,若没有重叠,就直接插入。整个过程类似于排序中的插入排序,O(n^2) time.

自然地,也可以想到使用更高效的“排序”算法,这里可以用增量式的reduce策略,而是采用分治,整个过程类似于归并排序,将问题分解为前n/2个元素构成的序列和后n/2个元素构成的序列。递归求解至n=1,可以直接得出天际线。关键在于如何merge两个子问题的解(不妨设为left和right)
* 使用i指向left,j指向right
* 取left[i]和right[j]的横坐标较小者为结果的横坐标,高度的较大者为结果的纵坐标

note:如果当前的高度和上一次插入结果的高度相同,那么跳过当前横坐标

class Solution
{
public:
    vector<vector<int>> getSkyline(vector<vector<int>> &buildings)
    {
        if (buildings.empty())
            return buildings;
        return cal(buildings, 0, buildings.size() - 1);
    }

private:
    vector<vector<int>> cal(vector<vector<int>> &buildings, int start, int end)
    {
        vector<vector<int>> res;
        if (end - start > 0)
        {
            int mid = (start + end) / 2;
            auto left = cal(buildings, start, mid);
            auto right = cal(buildings, mid + 1, end);
            int i = 0, j = 0, m = left.size(), n = right.size(), lh = 0, rh = 0;
            while (i < m && j < n)
            {
                if (left[i][0] < right[j][0])
                {
                    lh = left[i][1];
                    if (res.empty() || res.back()[1] != max(lh, rh))
                        res.emplace_back(vector<int>{left[i][0], max(lh, rh)});
                    i++;
                }
                else if (left[i][0] > right[j][0])
                {
                    rh = right[j][1];
                    if (res.empty() || res.back()[1] != max(lh, rh))
                        res.emplace_back(vector<int>{right[j][0], max(lh, rh)});
                    j++;
                }
                else
                {
                    lh = left[i][1];
                    rh = right[j][1];
                    if (res.empty() || res.back()[1] != max(lh, rh))
                        res.emplace_back(vector<int>{right[j][0], max(lh, rh)});
                    i++;
                    j++;
                }
            }
            while (i < m)
                res.emplace_back(left[i++]);
            while (j < n)
                res.emplace_back(right[j++]);
        }
        else
        {
            res.emplace_back(vector<int>{buildings[start][0], buildings[start][2]});
            res.emplace_back(vector<int>{buildings[start][1], 0});
        }
        return res;
    }
};

扫描线算法, O(nlogn) time

这道题本身也是一道经典的sweep line问题。

考虑结果中的天际线,除最后一个外,其余仅和building的起点相关,结果集中的元素:横坐标与起点的横坐标相关、纵坐标和当前高度相关(当前高度与之前的building也相关)

building的横坐标易求,对于当前高度可以维护一个队列,我们每次取最大的即可。由于对于高度队列,我们需要对元素进行删除(当遇到一个building的终点时,删除该building的高度)、插入(遇到一个新的building时,插入该building的高度)、取最大值。所以可以采用heap/multiset(高度可以重复)来存储,这里采用multiset。

整个算法过程如下:
* 将起点连同高度与终点连同高度各作为一个pair都统一保存到一个数组中,然后进行排序(排序规则为横坐标小的在前面,若横左边相同,则高度小的在靠前)。为区分起点和终点,将起点高度设为负值,这样的好处是如果有另外一个终点和起点的x坐标一样,排序之后起点会在前面,也就是在同一个x坐标处,我们会优先处理起点
* 采用扫描线算法依次处理我们前面排好序的数组中的元素。如果是起点,就将其高度放到multiset中;如果是终点,就在multiset中将其起点删除掉。接着还需要检查删除前后multiset中的最大值是否发生改变,如果发生改变了,则说明这个点就是边际点,将其加入结果集中。

note:实现时在multiset中首先添加一个0值,这样可以保证将边际的终点加入结果集中。

class Solution
{
public:
    vector<vector<int>> getSkyline(vector<vector<int>> &buildings)
    {
        if (buildings.empty())
            return buildings;
        vector<pair<int, int>> heights;
        for(auto building:buildings){
            heights.emplace_back(make_pair(building[0], -building[2]));
            heights.emplace_back(make_pair(building[1], building[2]));
        }
        sort(heights.begin(), heights.end());
        multiset<int> cur;
        vector<vector<int>> res;
        int preHeight = 0;
        cur.insert(0);
        for (int i = 0; i < heights.size();++i){
            if(heights[i].second<0)
                cur.insert(-heights[i].second);
            else{
                auto it = cur.find(heights[i].second);
                cur.erase(it);
            }
            if(*cur.rbegin()!=preHeight){
                preHeight = *cur.rbegin();
                res.emplace_back(vector<int>{heights[i].first, preHeight});
            }
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注