算法42：天际线问题（力扣218题）---线段树

2024-02-04 20:44
文章标签 算法 问题 力扣 42 线段 218 天际线

本文主要是介绍算法42：天际线问题（力扣218题）---线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

218. 天际线问题

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

  • lefti 是第 i 座建筑物左边缘的 x 坐标。
  • righti 是第 i 座建筑物右边缘的 x 坐标。
  • heighti 是第 i 座建筑物的高度。

你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

示例 1：

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。

示例 2：

输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]

分析：

这一题看起来很复杂，其实掌握了算法40和算法41的知识点以后，分析起来还是很容易的。

1. 首先，我们观察图片发现，天际线搜集的就是每个建筑物的开始坐标和结束坐标。开始坐标就是建筑物的高度。而结束坐标默认搜集高度为0.

2. 如果有第二个建筑物和第一个建筑物有部分重叠，那么第二个建筑物比第一个建筑物高的话，就搜集第二个建筑物开始位置的横坐标和高度；

如果第二个建筑物比第一个建筑物更宽，说明第二个建筑物把第一个建筑物个住当住了，第二个建筑物比第一个建筑物又高又宽，那么直接放弃第一个建筑物搜集的结束点的横坐标和高度信息；搜集第二个建筑物的坐标和高度替换第一个建筑物的结束点信息。当然，第二个建筑物的结束点高度为0.

3. 建筑物给的顺序，是X轴排好序的。因此，每添加一个建筑物，就搜集一下开始点。结束点是需要判断的；

4. 利用线段树的知识点，首先对X轴坐标进行搜集并确认区间；其次，每一个建筑物都有区间，区间的结束点都默认为0；0代表不更新，如果当前区间被之前的建筑物占领了位置，还保留之前的建筑物坐标信息。

5. 以本题第一个案例来分析，首先搜集X轴坐标并划分区间信息：

有了以上信息，我们接下来就是逐步推导的过程了：

由于天际点搜集的是每个区间的开始位置和结束位置；因此，存在连续、重复的信息应该忽略掉后一个重复值。最终搜集的是：

参照上图，根据区间获取X轴坐标值：

1 区间的 10       1区间对应X轴的2， 因此最终是 [2, 10]

2 区间的 15        2区间对应X轴的3， 因此最终是 [3, 15]

4 区间的 12        4区间对应X轴的7， 因此最终是 [7, 12]

6 区间的 0          6区间对应X轴的12， 因此最终是 [12, 0]

7 区间的 10        7区间对应X轴的15， 因此最终是 [15, 10]

9 区间的 8          9区间对应X轴的20， 因此最终是 [20, 8]

10 区间的 0        10区间对应X轴的24， 因此最终是 [24, 0]

最终结果就是 [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

代码实现：

package code04.线段树_02;import java.util.*;//力扣 216，天际线问题 https://leetcode.cn/problems/the-skyline-problem/
public class Code03_SkyLine_2 {class SegmentTree {int[] lines;SegmentTree(int size){lines = new int[size * 4];}//不使用懒更新public void add(int left,int right,int curIndex,int start,int end,int value){//叶子节点if (left == right) {if (left != end) {lines[curIndex] = value > lines[curIndex] ? value : lines[curIndex];}return;}int mid = (left + right)/2;if (start <= mid) {add(left, mid, curIndex * 2, start, end, value);}if (end > mid) {add(mid + 1, right, curIndex * 2 + 1, start, end, value);}}public void query(int left,int right,int curIndex,Map map,List<List<Integer>> list){//叶子节点if (left == right) {/*** 1. 为空直接放入* 2. 不为空，需要判断list最后一个元素*    即最后一个元素的下标为1的位置的值，是否与innerList*    下标为1的值相等。相等则排除，否则加入*/if (list.isEmpty()|| (!list.isEmpty()&& list.get(list.size() - 1) != null&& list.get(list.size() - 1).get(1) != lines[curIndex])) {List<Integer> innerList = new ArrayList<>();//横坐标innerList.add((Integer) map.get(left));//纵坐标innerList.add( lines[curIndex]);list.add(innerList);}return;}int mid = (left + right)/2;query(left, mid, curIndex * 2, map, list);query(mid + 1, right, curIndex * 2 + 1, map, list);}}//根据x轴，按照从左到右、从大到小的顺序编制区间下标public HashMap<Integer, Integer> index(int[][] positions){TreeSet<Integer> pos = new TreeSet<>();//离散化过程,统计开始、结束区间的坐标。//不管数组长度为多少，最终都是落在这些区间中的for (int[] arr : positions) {pos.add(arr[0]);pos.add(arr[1]);}int index = 1;HashMap<Integer, Integer> map = new HashMap<>();//给每个下标编个index，从1开始; 模拟原始线段树的原始数组中给每个元素添加下标的逻辑for (Integer key : pos) {map.put(key, index++);}return map;}//根据区间下标找对应的x轴坐标值public HashMap<Integer, Integer> reverseKeyValue (HashMap<Integer, Integer> map){HashMap reverseMap = new HashMap();for (Iterator iterator = map.keySet().iterator(); iterator.hasNext();) {int key = (int) iterator.next();int value = map.get(key);reverseMap.put(value, key);}return reverseMap;}public List<List<Integer>> getSkyline(int[][] buildings) {//获取到了X轴上对应的下标HashMap<Integer, Integer> map = index(buildings);int size = map.size();SegmentTree tree = new SegmentTree(size);//原始数组的范围int left = 1;int curIndex = 1;int right = size;for (int[] arr : buildings) {//任务的范围int start = map.get(arr[0]);int end = map.get(arr[1]);int value = arr[2];tree.add(left, right, curIndex, start, end, value);}List<List<Integer>> list = new ArrayList<>();HashMap<Integer, Integer> reverseMap = reverseKeyValue(map);tree.query(left, right, curIndex, reverseMap, list);return list;}public static void main(String[] args) {int[][] buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};Code03_SkyLine_2 ss = new Code03_SkyLine_2();System.out.println(ss.getSkyline(buildings));}
}

力扣测试结果：

一顿操作猛如虎，结果只打败了 5%，说明代码不够优秀，还需要优化。

优化：

目测我刚刚分析的图片

1、区间的最后一个高度根本就不做考虑，也就是说线段树更新 1 - N，实际上关注的就是 1 到 （N-1）的范围； 这样的话，add方法内部的 

if (left == right) {if (left != end) {lines[curIndex] = value > lines[curIndex] ? value : lines[curIndex];}return;
}

就可以直接去掉  if (left != end)  逻辑判断了。

2. 我们每添加一个建筑物，就递归到子节点。虽然线段树的时间复杂度为O(logN). 但是，执行1次和执行10次这样的时间复杂度方法，时间还是不一样的。因此，需要对目前的add方法进行优化，线段树的懒更新必须加进去

优化代码：

package code04.线段树_02;import java.util.*;//力扣 216，天际线问题 https://leetcode.cn/problems/the-skyline-problem/
public class Code03_SkyLine_2_opt {class SegmentTree {int[] lazy;SegmentTree(int size){lazy = new int[size * 4];}//不使用懒更新public void add(int left,int right,int curIndex,int start,int end,int value){if (start <= left && right <= end) {lazy[curIndex] = value > lazy[curIndex] ? value : lazy[curIndex];return;}int mid = (left + right)/2;pushDown(curIndex);if (start <= mid) {add(left, mid, curIndex * 2, start, end, value);}if (end > mid) {add(mid + 1, right, curIndex * 2 + 1, start, end, value);}}public void pushDown (int curIndex){if (lazy[curIndex] != 0) {lazy[curIndex*2] = lazy[curIndex] > lazy[curIndex * 2] ? lazy[curIndex] : lazy[curIndex * 2] ;lazy[curIndex*2+1] = lazy[curIndex] > lazy[curIndex * 2 + 1] ? lazy[curIndex] : lazy[curIndex * 2 + 1] ;lazy[curIndex] = 0;}}public void query(int left,int right,int curIndex,Map map,List<List<Integer>> list){//叶子节点if (left == right) {if (list.isEmpty()|| (!list.isEmpty()&& list.get(list.size() - 1) != null&& list.get(list.size() - 1).get(1) != lazy[curIndex])) {List<Integer> innerList = new ArrayList<>();//横坐标innerList.add((Integer) map.get(left));//纵坐标innerList.add(lazy[curIndex]);list.add(innerList);}return;}int mid = (left + right)/2;pushDown(curIndex);query(left, mid, curIndex * 2, map, list);query(mid + 1, right, curIndex * 2 + 1, map, list);}}//根据x轴，按照从左到右、从大到小的顺序编制区间下标public HashMap<Integer, Integer> index(int[][] positions){TreeSet<Integer> pos = new TreeSet<>();//离散化过程,统计开始、结束区间的坐标。//不管数组长度为多少，最终都是落在这些区间中的for (int[] arr : positions) {pos.add(arr[0]);pos.add(arr[1]);}int index = 1;HashMap<Integer, Integer> map = new HashMap<>();//给每个下标编个index，从1开始; 模拟原始线段树的原始数组中给每个元素添加下标的逻辑for (Integer key : pos) {map.put(key, index++);}return map;}//根据区间下标找对应的x轴坐标值public HashMap<Integer, Integer> reverseKeyValue (HashMap<Integer, Integer> map){HashMap reverseMap = new HashMap();for (Iterator iterator = map.keySet().iterator(); iterator.hasNext();) {int key = (int) iterator.next();int value = map.get(key);reverseMap.put(value, key);}return reverseMap;}public List<List<Integer>> getSkyline(int[][] buildings) {//获取到了X轴上对应的下标HashMap<Integer, Integer> map = index(buildings);int size = map.size();SegmentTree tree = new SegmentTree(size);//原始数组的范围int left = 1;int curIndex = 1;int right = size;for (int[] arr : buildings) {//任务的范围int start = map.get(arr[0]);int end = map.get(arr[1]);int value = arr[2];//天际线的区间最后一个x坐标的高度信息根本不做考虑，默认就是0.// 因此，start - end的区间，实际考虑的知识 start - (end-1)的范围tree.add(left, right, curIndex, start, end - 1, value);}List<List<Integer>> list = new ArrayList<>();HashMap<Integer, Integer> reverseMap = reverseKeyValue(map);tree.query(left, right, curIndex, reverseMap, list);return list;}public static void main(String[] args) {//int[][] buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};//int[][] buildings = {{0,2,3},{2,5,3}};int[][] buildings = {{2,13,10},{10,17,25},{12,20,14}};Code03_SkyLine_2_opt ss = new Code03_SkyLine_2_opt();System.out.println(ss.getSkyline(buildings));}
}

测试结果：打败76%

分析这个问题并且实现第一版代码只花了半天时间，但是优化出第二版代码却花了一整天。

不管是什么算法和数据结构，光掌握原理是远远不够的。熟能生巧，多练、多思考，才能快速写出优秀的代码，这是不可缺少的流程。共勉之！

这篇关于算法42：天际线问题（力扣218题）---线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/678750。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
hdu1689(线段树成段更新)

hdu1689(线段树成段更新)

两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2