首页 > 试题广场 >

大楼轮廓问题

[编程题]大楼轮廓问题
  • 热度指数:729 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个的矩阵matrix,对于每一个长度为3的小数组arr,都表示一个大楼的三个数据。arr[0]表示大楼的左边界,arr[1]表示大楼的右边界,arr[2]表示大楼的高度(一定大于0)。每座大楼的地基都在X轴上,大楼之间可能会有重叠,请返回整体的轮廓线数组
[要求]
时间复杂度为

输入描述:
第一行一个整数N,表示大楼的数量。

接下来N行,每个三个整数,表示第i个大楼的信息


输出描述:
输出若干行,每行有3个整数,表示最终的轮廓线。
示例1

输入

8
2 5 6
1 7 4
4 6 7
3 6 5
10 13 2
9 11 3
12 14 4
10 12 5

输出

1 2 4
2 4 6
4 6 7
6 7 4
9 10 3
10 12 5
12 14 4

说明

给出的楼房信息以及最后的轮廓线如下图所示





备注:

为了描述所有建筑构建的轮廓线,我们需要求得每个坐标点上面的最大高度。每个大楼构建两个关键点,信息体结构如下:
  1. 坐标
  2. 是否是加入一个高度
  3. 大楼高度
于是对于某个大楼[x,y,h],我们可以得到两个关键点:(1) 大楼的起始坐标x、当前坐标是加入高度、高度为h;(2) 大楼的结束坐标y、当前坐标是删除高度、高度为h。于是n栋大楼可以构建2n个关键点来描述。按大楼的起始坐标进行排序(如果坐标相同,将加入高度的关键点排在前面,防止有“线状”大楼的存在)。
建立两个有序表,一个用于统计高度的频数mapHeightTimes,另一个用于记录某一位置的最大高度mapXvalueHeight。然后开始遍历排完序后的关键点,对一个关键点,我们有如下的两个操作:(1) 遇到增加高度的关键点就增加高度频数,否则减少高度频数;(2) 通过mapHeightTimes得到迄今为止的最大高度,它就是当前位置的最大高度(如果当前遍历到的是删除高度的关键点,就会终结这个高度的大楼对当前坐标点最大高度的影响,删除这个高度之后,高度频数表中的最大高度一定是当前坐标点的最大高度)。需要注意的是,在进行遍历的过程中,我们还需要保存好前一个高度,这样才能够描述出轮廓线的线段。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;
import java.util.Map.Entry;

class Node {
    public int x;
    public boolean isAdd;
    public int height;
    public Node(int x, boolean isAdd, int height) {
        this.x = x;
        this.isAdd = isAdd;
        this.height = height;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Node[] buildings = new Node[2 * n];
        Node node;
        for(int i = 0; i < n; i++){
            String[] params = br.readLine().split(" ");
            node = new Node(Integer.parseInt(params[0]), true, Integer.parseInt(params[2]));
            buildings[i] = node;
            node = new Node(Integer.parseInt(params[1]), false, Integer.parseInt(params[2]));
            buildings[i + n] = node;
        }
        Arrays.sort(buildings, new Comparator<Node>() {
            @Override
            public int compare(Node node1, Node node2) {
                return node1.x != node2.x? node1.x - node2.x: node1.isAdd? -1: 1;
            }
        });
        TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
        TreeMap<Integer, Integer> mapXvalueHeight = new TreeMap<>();
        for(int i = 0; i < 2*n; i++){
            if(buildings[i].isAdd){
                mapHeightTimes.put(buildings[i].height, mapHeightTimes.getOrDefault(buildings[i].height, 0) + 1);
            }else{
                if(mapHeightTimes.get(buildings[i].height) == 1){
                    mapHeightTimes.remove(buildings[i].height);
                }else{
                    mapHeightTimes.put(buildings[i].height, mapHeightTimes.get(buildings[i].height) - 1);
                }
            }
            if(mapHeightTimes.isEmpty()){
                mapXvalueHeight.put(buildings[i].x, 0);    // 没有高度了,当前坐标x的最大高度为0
            }else{
                mapXvalueHeight.put(buildings[i].x, mapHeightTimes.lastKey());    // 否则是加入过的最大高度
            }
        }
        int preX = 0, preHeight = 0;
        for(Entry<Integer, Integer> entry: mapXvalueHeight.entrySet()) {
            // 当前位置及其最大高度
            int curX = entry.getKey();
            int curHeight = entry.getValue();
            if(curHeight != preHeight){
                // 高度改变时更新轮廓线
                if(preHeight != 0) System.out.println(preX + " " + curX + " " + preHeight);
                preX = curX;
                preHeight = curHeight;
            }
        }
    }
}

发表于 2021-12-02 16:01:18 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct P{
    int x, t, h;
};

bool cmp(P p1, P p2){
    return p1.x < p2.x;
}

int main(){
    int n, x, y, h;
    cin>>n;
    P p[100003];
    for(int i=0;i<n;i++){
        cin>>x>>y>>h;
        int l = 2*i, r=2*i+1;
        p[l].x = x;
        p[r].x = y;
        p[l].h = p[r].h = p[r].t = h;
    }
    sort(p, p+2*n, cmp);
    map<int, int> M;
    M[0] = 1;
    for(int i=0,pre_h=0,pre_x=-1;i<2*n;){
        x = p[i].x;
        for(;i<2*n && p[i].x==x;i++){
            if(p[i].t==0)
                M[p[i].h]++;
            else if(--M[p[i].h]==0)
                M.erase(p[i].h);
        }
        h = M.rbegin()->first;
        if(pre_h && pre_h!=h)
            cout<<pre_x<<" "<<x<<" "<<pre_h<<endl;
        if(pre_h!=h){
            pre_h = h;
            pre_x = x;
        }
    }
    return 0;
}

发表于 2020-03-11 03:41:00 回复(0)
提供一种双堆,实现策略:每一栋大楼包含两个关键点(左 右)
先按照x下标排序所有关键点;初始化一个最大堆
每遇到一个左关键点,push  同时分析当前楼是否更高了(如果是 输出前一部分的区间和高度)
每遇到一个右关键点,需要将堆中对应的左关键点删除(双堆实现) 同时分析高度是否降低了(如果是,输出前一部分区间)

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int x;  //所在x下标
    int y;  //所在高度
    int left_or_right;//是一个长方形的 左边=0  右边=1
    node(int _x,int _y,int which)
    {
        x=_x;
        y=_y;
        left_or_right=which;
    }
};
bool static cmp1(node a,node b)
{
    return a.x<b.x;  //关键点left=>right 按照下标排序
}

class my_heap
{
    private:
     priority_queue<int> q1;
     priority_queue<int> q2;  //两个最大堆
    public:
    void push(int _v)
    {
        q1.push(_v);
    }
    void erase(int _v) //任意节点删除
    {
        q2.push(_v);//在待删除堆中插入该值即可
    }
    void pop()  //删除过程 首先
    {
        while(q1.top()==q2.top()) //如果q2的堆顶(那些被任意删除的元素)==q1的堆顶  不断一起弹出
        {
            q1.pop();
            q2.pop();
        }
        q1.pop(); //最后弹出 
    }
    int top()  //获取最大最
    {
        while(q1.empty()==false &&q2.empty()==false && q1.top()==q2.top())
        {
            q1.pop();
            q2.pop();
        }
        if(q1.empty())
            return 0;
        else
            return q1.top();
    }
    bool empty()   //当前堆是否为空
    {
        return q1.size()==0 || q1.size()==q2.size();
    }
};
int main()
{
    int n;
    cin>>n;
    int l,r,h;
    vector<node> node_arr;//存放关键点
    for(int i=0;i<n;i++)
    {
        cin>>l>>r>>h;
        node_arr.push_back(node(l,h,0));
        node_arr.push_back(node(r,h,1));   //每个大楼都有两个关键节点
    }
    sort(node_arr.begin(),node_arr.end(),cmp1);
    //初始化两个最大堆  以支持任意节点的删除
    my_heap skyline;
    int len=node_arr.size();
    int height=0;//当前楼最大高度
    int index=0;//当前最大高度的左起点
    for(int i=0;i<len;i++)  //开始从左往右扫描关键点
    {
        if(node_arr[i].left_or_right==0)  //左边节点
        {
           skyline.push(node_arr[i].y);  //放入最大堆中
           int now_height=skyline.top();//当前的最大高度
            if(now_height>height) //新加入楼更高了
            {
                if(height>0 && node_arr[i].x>index)
                     cout<<index<<" "<<node_arr[i].x<<" "<<height<<endl;//输出前一部分高度
                //同时更新新的区间起点信息
                index=node_arr[i].x;
                height=node_arr[i].y;
                
            }
            
            
        }
        else  //遇到右边关键点
        {
            skyline.erase(node_arr[i].y);//删除该节点
            if(skyline.top()<height)  //若删除之后 天际线变低了
            {
                if(node_arr[i].x>index)
                     cout<<index<<" "<<node_arr[i].x<<" "<<height<<endl;
                //更新区间的起点信息
                index=node_arr[i].x;
                height=skyline.top();
                
            }
        }
    } 
}



发表于 2020-11-21 11:31:37 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct Node{
    int posi;
    int h;
    int isUp;
    Node(int p, int g, int is){
        posi = p;
        h = g;
        isUp = is;
    }
};
bool cmp(const Node &a, const Node &d){
    if (d.posi != a.posi)
        return a.posi < d.posi;
    else if (d.isUp != a.isUp)
        return a.isUp > d.isUp;
    else
        return a.h < d.h;
}

int main(){
    int n; scanf("%d", &n);
    vector<Node> nodes(n*2, Node(0,0,0));
    for(int i=0; i<n; i++){
        int s, e, h; scanf("%d%d%d", &s, &e, &h);
        nodes[2*i] = Node(s, h, 1);
        nodes[2*i+1] = Node(e, h, 0);
    }
    sort(nodes.begin(), nodes.end(), cmp);
    map<int, int> hmap; //(h, time)
    map<int, int> pmap; //(posi, h)
    for(int i=0; i<n*2; i++){
        if(nodes[i].isUp == 1){
            if(hmap.count(nodes[i].h) == 0){
                hmap[nodes[i].h] = 1;
            } else{
                hmap[nodes[i].h] += 1;
            }
        } else{
            hmap[nodes[i].h] -= 1;
            if(hmap[nodes[i].h] == 0){
                hmap.erase(nodes[i].h);
            }
        }
        if (hmap.empty()) {
            pmap[nodes[i].posi] = 0;
        } else {
            pmap[nodes[i].posi] = (--hmap.end())->first;
        }
    }
    int start = 0;
    int preHeight = 0;
    std::map<int, int>::iterator it;
    for(it=pmap.begin(); it!=pmap.end(); it++){
        int curIndex = it->first;
        int curHeight = it->second;
        if(curHeight != preHeight){
            if(preHeight != 0){
                cout << start <<" ";
                cout << curIndex << " ";
                cout << preHeight << endl;
            }
            start = curIndex;
            preHeight = curHeight;
        }
    }
    return 0;
}

编辑于 2020-02-10 00:40:03 回复(1)