给定一个的矩阵matrix,对于每一个长度为3的小数组arr,都表示一个大楼的三个数据。arr[0]表示大楼的左边界,arr[1]表示大楼的右边界,arr[2]表示大楼的高度(一定大于0)。每座大楼的地基都在X轴上,大楼之间可能会有重叠,请返回整体的轮廓线数组
[要求]
时间复杂度为
第一行一个整数N,表示大楼的数量。
接下来N行,每个三个整数,表示第i个大楼的信息
输出若干行,每行有3个整数,表示最终的轮廓线。
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
给出的楼房信息以及最后的轮廓线如下图所示
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; } } } }
#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; }
#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(); } } } }
#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; }