力扣218.天际线问题 线段树解法
原题
官解用的扫描线 + 优先队列方法，但是一开始没想的那么麻烦，只觉得这么有多区间，直觉暴力线段树，也提供一种思路
class Solution {//用线段树的结点范围代表x轴 结点值代表这段x轴内的最高高度//建完树之后如何获得答案呢？ 再次遍历buildings数组//遍历每个建筑的左上点和右下点 如果其是这个区间最高点 就加入答案public List<List<Integer>> getSkyline(int[][] buildings) { //buildings[i] = [lefti, righti, heighti]int n = buildings.length;N = 1;for (int i = 0; i < n; i++) {N = Math.max(N, buildings[i][1]);// 找出线段树的范围 可以省一点时间}// 注意！区间最值的更新，为了避免覆盖情况，比如[15,20,10]和[19,24,8]，需要按区间高度先排序Arrays.sort(buildings, (o1,o2) -> o1[2]-o2[2]);//按高度从小到大排序 这样就不会产生错误覆盖List<Integer> points = new ArrayList<>(); //存储边界坐标点for (int[] building : buildings) {int l = building[0],r=building[1],h=building[2];points.add(l);points.add(r);update(root,0,N,l,r-1,h);//建树 注意！ 右边界的高度不算 防止端点覆盖}Collections.sort(points);//对坐标点排序points = points.stream().distinct().collect(Collectors.toList());//去除重复坐标点List<List<Integer>> ans = new ArrayList<>();//答案数组for (int i = 1; i < points.size(); i++) {int heigh=(int)query(root,0,N,points.get(i-1),points.get(i)-1);int j=i+1;while (j<points.size() && query(root,0,N,points.get(j-1),points.get(j)-1)==heigh) j++;//相同高度不算在天际线里ans.add(Arrays.asList(points.get(i-1),heigh));i = j-1;}ans.add(Arrays.asList(points.get(points.size()-1),0));//最后一个点坐标单独判断return ans;}//下面为线段树模版class Node {Node left, right;long val, add;}private int N;//线段树范围大小private Node root = new Node();public void update(Node node, long start, long end, long l, long r, long val) {if (l <= start && end <= r) {node.val = val;node.add = val;return;}long mid = (start + end) >> 1;pushDown(node, mid - start + 1, end - mid);if (l <= mid) update(node.left, start, mid, l, r, val);if (r > mid) update(node.right, mid + 1, end, l, r, val);pushUp(node);}// 在区间 [start, end] 中查询区间 [l, r] 的结果public long query(Node node, long start, long end, long l, long r) {if (l <= start && end <= r) return node.val;long mid = (start + end) >> 1, ans = 0;pushDown(node, mid - start + 1, end - mid);if (l <= mid) ans = query(node.left, start, mid, l, r);if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));return ans;}// 向上更新private void pushUp(Node node) {node.val = Math.max(node.left.val, node.right.val);}// 推懒惰标记的函数private void pushDown(Node node, long leftNum, long rightNum) {if (node.left == null) node.left = new Node();if (node.right == null) node.right = new Node();if (node.add == 0) return;node.left.val = node.add;node.right.val = node.add;node.left.add = node.add;node.right.add = node.add;node.add = 0;}
}