郑州网站建设华久,媒体软文发稿,成都网站建设询q479185700上快,网站域名虚拟主机#xff08;思路感觉挺明显的#xff0c;就是一些特殊情况得考虑清楚#xff09;
题目#xff1a; 城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度#xff0c;请返回 由这些建筑物形成的 天际线 。 每个建筑物的几何信息…思路感觉挺明显的就是一些特殊情况得考虑清楚
题目 城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度请返回 由这些建筑物形成的 天际线 。 每个建筑物的几何信息由数组 buildings 表示其中三元组 buildings[i] [lefti, righti, heighti] 表示 lefti 是第 i 座建筑物左边缘的 x 坐标。 righti 是第 i 座建筑物右边缘的 x 坐标。 heighti 是第 i 座建筑物的高度。 你可以假设所有的建筑都是完美的长方形在高度为 0 的绝对平坦的表面上。 天际线 应该表示为由 “关键点” 组成的列表格式 [[x1,y1],[x2,y2],…] 并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点y 坐标始终为 0 仅用于标记天际线的终点。此外任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。 注意输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案三条高度为 5 的线应该在最终输出中合并为一个[…[2 3], [4 5], [12 7], …]
题解 这道题主要就是和位置高度相关
① 那我们如果不考虑高度主要考虑位置可以吗
比如我们把高度从低到高排个序 然后按顺序考虑建筑物 相当于每次考虑当前建筑物可以直接把之前建筑物给覆盖掉因为之前考虑的建筑肯定更矮
好像不可行没有数据结构可以这样操作 如果用数组直接保存每个位置当前的最高点也不行0 lefti righti 2^31 - 1 范围太大了
② 那我们如果不考虑位置主要考虑高度可以吗
就是按照建筑物左边位置从左到右依次考虑建筑物即扫描线从左到右移过去 建筑物右边位置则通过 pair右边高度右边位置 存储
建筑物右边位置放入一个集合中存储代表当前还有这些建筑物被扫描线压到 然后考虑最高的一个矮的会被覆盖 所以采用优先队列 其实有些没有被扫描线压到的也被放在了里面可能没有及时拿出来到时候直接对比扫描线如果在扫描线左边直接抛弃就可以
然后每次扫描线移动到建筑物左边位置时对比优先队列中扫描线压到的最高建筑物 如果优先队列中的那个更高则这个当前被覆盖了把它的右边位置扔到优先队列就没事了 如果当前建筑物的左边更高则把这个位置当成天际线的一点并也把它右边位置扔到优先队列里
考虑特殊情况
优先队列中的没有被扫描线压到抛弃的时候也可能形成天际线一点如果多个天际线上点在同一直线上[0, 2][1, 2][1, 4]例 x 1 时有 y 2 和 y 4则需要考虑前一个点x 0如果 x 1 的 y 最大值大于 x 0 的 y则取 y 最大值否则取 y 最小值
代码如下
class Solution {
public:priority_queuepairint, int temp_right;vectorvectorint res_temp;vectorvectorint res;vectorvectorint getSkyline(vectorvectorint buildings) {int f -1;vectorint t(2);pairint, int flag;for(int i 0; i buildings.size(); i) {while(!temp_right.empty()) {flag temp_right.top();if(flag.second f) {temp_right.pop();}else if(flag.second buildings[i][0]) {temp_right.pop();while(!temp_right.empty() flag.second temp_right.top().second) {temp_right.pop();}if(!temp_right.empty()) {t[0] flag.second;t[1] temp_right.top().first;}else {t[0] flag.second;t[1] 0;}res_temp.push_back(t);f t[0];}else {if(flag.first buildings[i][2]) {t[0] buildings[i][0];t[1] buildings[i][2];res_temp.push_back(t);f t[0];}break;}}if(temp_right.empty()) {t[0] buildings[i][0];t[1] buildings[i][2];res_temp.push_back(t);f t[0];}temp_right.push(make_pair(buildings[i][2], buildings[i][1]));}while(!temp_right.empty()) {flag temp_right.top();temp_right.pop();while(!temp_right.empty() flag.second temp_right.top().second) {temp_right.pop();}if(f flag.second) {if(!temp_right.empty()) {t[0] flag.second;t[1] temp_right.top().first;}else {t[0] flag.second;t[1] 0;}res_temp.push_back(t);f t[0];}}int p res_temp[0][0], p1 res_temp[0][1], p2 res_temp[0][1];for(int i 0; i res_temp.size(); i) {if(res_temp[i][0] ! p) {if(res.empty()) {t[0] p;t[1] p1;res.push_back(t);}else {if(p1 res[res.size() - 1][1]) {t[0] p;t[1] p1;res.push_back(t);}else {t[0] p;t[1] p2;res.push_back(t);}}p res_temp[i][0];p1 res_temp[i][1];p2 res_temp[i][1];}else {p1 max(p1, res_temp[i][1]);p2 min(p2, res_temp[i][1]);}}if(p1 res[res.size() - 1][1]) {t[0] p;t[1] p1;res.push_back(t);}else {t[0] p;t[1] p2;res.push_back(t);}return res;}
};
