解题报告:The Skyline Problem(画天际线)

题目出处:https://leetcode.com/problems/the-skyline-problem/

题目描述:

输入三元组[Li, Ri, Hi],代表建筑的左右坐标,以及高度,构成图A。

要求画出天际线,如B图所示,输出为[[x1,y1], [x2, y2], [x3, y3], ... ],一串二元组的集合,分别为轮廓的左端点,x代表横坐标,y代表纵坐标高度。

解题思路:

思路一:

首先,看到这道题,最最简单的思路是直接遍历每个x值,简单粗暴正面刚,将每个覆盖x值的区间合并并求出最大值,从而画出天际线,找到左端点。但这个思路显然要跪,毕竟最先想到的90%都有问题,这个思路的空间复杂度为O(m) ,时间复杂度为O(nm)(m为最大x值,n为区间个数),所以放弃这个思路,继续思考。

思路二:

1、通过简单的分析,我们可以发现,对于天际线起作用的实际上是建筑的顶边(就是上面那条边,原谅我语文表达不好),而顶边则是由左右端点确定的,所以我们只需要存储每个建筑的左右端点。考虑如何存储端点,应该将端点按照x坐标值由小到大排序,同时如果x相等,对于左端点,按照高度由低到高;对于右端点,按照高度由高到低排序。考虑使用什么数据结构存储端点,由于排序以及后面访问端点时,需要知道是左端点还是右端点。所以,我们建立Node类,使用vector存储点,同时重载sort函数进行排序(想到这里,就觉得好麻烦有没有(>﹏<))

2、将端点排序储存之后,我们一个一个访问端点。如果是左节点,就记录高度信息,如果高度大于之前的高度,就说明这个节点是个拐点,记录在ans(vector<pair<int, int>>类型)中;遇到右节点时,就需要将对应的左节点的高度删掉。

于是我们需要存储高度信息,而且还要实现按照大小排序的功能。到底用什么数据结构呢?好蛋疼......set不可以,可能会重复;vector没有排序;通过查文档,发现了priority_queue(好像老师上课讲过,果然没有好好听课0.0),但是这个没法删除,简直B了狗了,可能还需要flag标记要删除的信息,于是有需要map将flag映射到高度信息(果然是数据结构的题。。。。);继续找,发现了multiset,就决定是你了!我们用cur,pre分别代表当前及之前的最大高度,最终得到ans,就是结果。

代码如下:

class Solution {
private:
    struct node {
        int x, y;
        string type;
        node(int _x, int _y, string _type) : x(_x), y(_y), type(_type) {}
    };

public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings)
    {
        vector<node> height;
        for (int i = 0; i < buildings.size(); i++)
        {
            height.push_back(node(buildings[i][0], buildings[i][2], "LEFT"));
            height.push_back(node(buildings[i][1], buildings[i][2], "RIGHT"));
        }
        sort(height.begin(), height.end(),f);
        multiset<int> heap;
        heap.insert(0);
        vector<pair<int, int>> res;
        int pre = 0, cur = 0;
        for (int i = 0; i < height.size(); i++)
        {
            if (height[i].type == "LEFT")
            {
                heap.insert(height[i].y);
            }
            else
            {
                heap.erase(heap.find(height[i].y));
            }
            cur = *heap.rbegin();
            if (cur != pre)
            {
                res.push_back({height[i].x, cur});
                pre = cur;
            }
        }
        return res;
    }
    static bool f(const node &a, const node &b)
    {
        if (a.x != b.x)
            return a.x < b.x;
        else if (a.type == "LEFT" && b.type == "LEFT")
            return a.y > b.y;
        else if (a.type == "RIGHT" && b.type == "RIGHT")
            return a.y < b.y;
        else
            return a.type == "LEFT";
    }
};

感觉解释的挺清楚的,就没有加注释(我不会告诉你其实是因为我懒(¬_¬))。提交到OJ上,已经可以AC。

本来呢,已经结束了,但是看了@bill_liu的博客,深受启发,手动感谢@bill_liu,@GDP。借用朋神的思路,可以将左节点的高度设为负值加入到点的集合中,这样就可以区分左右结点,而且神奇的发现,这样不需要重写sort函数,也符合比较结果(将端点按照x坐标值由小到大排序,同时如果x相等,对于左端点,按照高度由低到高;对于右端点,按照高度由高到低排序),这样我们不需要重新建Node类,只需要pair存储点即可。

修正代码:

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings)
    {
        vector<pair<int, int>> height;
        for (int i = 0; i < buildings.size(); i++)
        {
            height.push_back({buildings[i][0], -buildings[i][2]});
            height.push_back({buildings[i][1], buildings[i][2]});
        }
        sort(height.begin(), height.end());
        multiset<int> heap;
        heap.insert(0);
        vector<pair<int, int>> res;
        int pre = 0, cur = 0;
        for (int i = 0; i < height.size(); i++)
        {
            if (height[i].second < 0)
            {
                heap.insert(-height[i].second);
            }
            else
            {
                heap.erase(heap.find(height[i].second));
            }
            cur = *heap.rbegin();
            if (cur != pre)
            {
                res.push_back({height[i].first, cur});
                pre = cur;
            }
        }
        return res;
    }
};

代码简洁了许多,有没有~

总结:

这个题确实很难,首先需要抽象出来线段,点,以及明确记录的是什么情况下的点。还有就是选取合适的数据结构,包括使用正负区分左右端点。

嗯,就这样了,(撸完大作业)有时间再想别的思路,晚安~~

同刘斌,为何对于这道题,从OJ上的提交数据来看,用python,java等写出来的运行速度比用C,C++写出来的快得多?求大神解答

时间: 11-27

解题报告:The Skyline Problem(画天际线)的相关文章

解题报告 之 HDU5328 Problem Killer

解题报告 之 HDU5328 Problem Killer Description You are a "Problem Killer", you want to solve many problems. Now you have  problems, the -th problem's difficulty is represented by an integer  (). For some strange reason, you must choose some integer  

解题报告:LeetCode The Skyline Problem(画天际

题目出处:https://leetcode.com/submissions/detail/47013144/题意描述: 给定一系列矩形的左边坐标Li,右边坐标Ri,和高度Hi(其中Li按照从小到大的顺序排列).代表城市中一座座高楼.求这些矩形代表的高楼行成的天际线.天际线的定义为:在远处看这些所有的高楼时看到的轮廓. 数据输入: [ [L1, R1, H1], [Li, Ri, Hi]...]为元素类型为三维向量的向量,其中Li,Ri,Hi的含义见题意描述.且输入数据保证: 0 ≤ Li, Ri

hdu - 5349 MZL&#39;s simple problem(解题报告)

A - MZL's simple problem Time Limit:1500MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Description A simple problem Problem Description You have a multiple set,and now there are three kinds of operations: 1 x : add number

[poj 2480] Longge&#39;s problem 解题报告 (欧拉函数)

题目链接:http://poj.org/problem?id=2480 题目大意: 题解: 我一直很欣赏数学题完美的复杂度 #include<cstring> #include<algorithm> #include<cstdio> #include<iostream> #include<cmath> using namespace std; typedef long long ll; const int N=(1<<31)+15;

2020-3-14 acm训练联盟周赛Preliminaries for Benelux Algorithm Programming Contest 2019 解题报告+补题报告

2020-3-15比赛解题报告+2020-3-8—2020-3-15的补题报告 2020-3-15比赛题解 训练联盟周赛Preliminaries for Benelux Algorithm Programming Contest 2019  A建筑(模拟) 耗时:3ms 244KB 建筑 你哥哥在最近的建筑问题突破大会上获得了一个奖项 并获得了千载难逢的重新设计城市中心的机会 他最喜欢的城市奈梅根.由于城市布局中最引人注目的部分是天际线, 你的兄弟已经开始为他想要北方和东方的天际线画一些想法

poj 3020 Antenna Placement 解题报告

题目链接:http://poj.org/problem?id=3020 题目意思:首先,请忽略那幅有可能误导他人成分的截图(可能我悟性差,反正有一点点误导我了). 给出一幅 h * w 的图,  “ * ” 表示 point of interest,“ o ” 忽略之.你可以对 " * " (假设这个 “* ”的坐标是 (i, j))画圈,每个圈只能把它四周的某一个点括住(或者是上面(i-1, j) or 下面(i+1, j) or 左边(i, j-1)  or 右边(i, j+1))

poj1328解题报告(贪心、线段交集)

POJ 1328,题目链接http://poj.org/problem?id=1328 题意: 有一海岸线(x轴),一半是陆地(y<0).一半是海(y>0),海上有一些小岛(用坐标点表示P1.P2...),现要在海岸线上建雷达(覆盖半径R).给出所有小岛的位置,和雷达半径,求最少需要多少个雷达? 思路: 1. 知道小岛位置,和雷达半径,那么以小岛为圆心,雷达覆盖半径为半径画圆,可以求出小岛与x轴有0(雷达无法覆盖).1(雷达只能在这个点上才能覆盖).2个交点(雷达在两点之间都能覆盖该小岛) 2

ACdream 1203 - KIDx&#39;s Triangle(解题报告)

KIDx's Triangle Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others) Submit Statistic Next Problem Problem Description One day, KIDx solved a math problem for middle students in seconds! And than he created this problem. N

解题报告 之 UVA563 Crimewave

解题报告 之 UVA563 Crimewave Description Nieuw Knollendam is a very modern town. This becomes clear already when looking at the layout of its map, which is just a rectangular grid of streets and avenues. Being an important trade centre, Nieuw Knollendam a

Winter-2-STL-E Andy&#39;s First Dictionary 解题报告及测试数据

use stringstream Time Limit:3000MS     Memory Limit:0KB Description Andy, 8, has a dream - he wants to produce his very own dictionary. This is not an easy task for him, as the number of words that he knows is, well, not quite enough. Instead of thin