给定一个的矩阵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; } } } }