大楼轮廓

题目描述

水平面上有 N 座大楼，每座大楼都是矩阵的形状，可以用三个数字表示 (start, end, height)，分别代表其在x轴上的起点，终点和高度。大楼之间从远处看可能会重叠，求出 N 座大楼的外轮廓线。
外轮廓线的表示方法为若干三元组，每个三元组包含三个数字 (start, end, height)，代表这段轮廓的起始位置，终止位置和高度。

思路

扫描法
1、将每栋大楼的开始坐标和高度作为节点，终止坐标和高度作为节点，可以用一个class来描述。
注意：节点class还需要增加当前节点是开始节点还是终止节点
所以，先通过给定的数据构造这些节点对象，将节点对象根据坐标较小的规则添加到堆中，堆使用PriorityQueue，自己创建比较器Comparator
2、从堆中弹出节点，从左到右开始扫描每一个节点
对于开始节点，将高度保存到一个堆中，根据高度决定是否已经扫描出了一个轮廓。
对于终止节点，根据高度判断是否已经扫描出了一个轮廓，再将该高度从堆中删除
3、最后一个节点扫描完后，即将所有的轮廓都扫描出来了

代码

public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
		
		ArrayList<ArrayList<Integer>> res = new ArrayList<>();
		
		// 将首尾坐标节点加入堆
		PriorityQueue<Node> priorityQueue = new PriorityQueue<>(new MyComparator());
		int number = 0;		// 大楼编号
		for(int[] building : buildings) {
			priorityQueue.add(new Node(building[0], building[2], true, number));
			priorityQueue.add(new Node(building[1], building[2], false, number));
			number++;
		}
		
		// 从第一个节点开始扫描
		PriorityQueue<Integer> hight = new PriorityQueue<>(new MyReverseComparator());		// 保存当前有效的高度的堆
		Node first = priorityQueue.poll();
		hight.add(first.high);
		int start = first.index;		// 始终指向扫描通过的线段的开端
		
		// 开始向后扫描
		while(!priorityQueue.isEmpty()) {
			Node node = priorityQueue.poll();
			if(node.isStart) {		// 线段的开端节点
				if(hight.isEmpty()) {
					hight.add(node.high);
					continue;
				}
				if(node.high > hight.peek()) {		// 扫描到更高的开端节点
					res.add(new ArrayList<Integer>(Arrays.asList(start, node.index, hight.peek())));
					start = node.index;		// 更新start指向
				}
				hight.add(node.high);		// 将线段的开端节点的高度加入堆
			}else {		// 线段的尾部节点
				if(node.high == hight.peek()) {		// 尾部节点即当前最高的线段的尾部节点
					res.add(new ArrayList<Integer>(Arrays.asList(start, node.index, hight.peek())));
					start = node.index;		// 更新start指向
				}
				hight.remove(node.high);		// 移除这段线段
			}
		}
		
		return res;
	}
	
	class MyComparator implements Comparator<Node> {

	@Override
	public int compare(Node arg0, Node arg1) {
		return (arg0.index - arg1.index) > 0 ? 1 : 
			 (arg0.index - arg1.index) < 0 ? -1 : 0; 
	}
	
}

class MyReverseComparator implements Comparator<Integer> {

	@Override
	public int compare(Integer o1, Integer o2) {
		// TODO Auto-generated method stub
		return o1 < 02 ? 1 : o1 > o2 ? -1 : 0;
	}
	
}


class Node {
	public int index;	// 节点位置
	public int high;
	public boolean isStart;
	public int number;		// 大楼编号
	
	public Node(int index, int high, boolean isStart, int number) {
		this.index = index;
		this.high = high;
		this.isStart = isStart;
		this.number = number;
	}
}

考差点

• 堆
• 扫描法