算法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%

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/370725.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

#RAG|NLP|Jieba|PDF2WORD# pdf转word-换行问题

文档在生成PDF时,文宁都发生了什么。本文讲解了配置对象、resources对象和content对象的作用,以及字体、宇号、坐标、文本摆放等过程。同时,还解释了为什么PDF转word或转文字都是一行一行的以及为什么页眉页脚的问题会加大识别难度。最后提到了文本的编码和PDF中缺少文档结构标…

五、RHCE--Web服务器

五、RHCE--Web服务器 1、web服务器简介&#xff08;1&#xff09;什么是www&#xff08;2&#xff09;网址及HTTP简介 2、web服务器的类型&#xff08;1&#xff09;仅提供用户浏览的单向静态网页&#xff08;2&#xff09;提供用户互动接口的动态网站 3、虚拟主机配置实战3.1 …

sqlserver alwayson部署文档手册

1、ALWAYSON概述 详细介绍参照官网详细文档,我就不在这里赘述了&#xff1a; https://learn.microsoft.com/zh-cn/sql/database-engine/availability-groups/windows/overview-of-always-on-availability-groups-sql-server?viewsql-server-ver16 下图显示的是一个包含一个…

【iOS ARKit】3D人体姿态估计实例

与2D人体姿态检测一样&#xff0c;在ARKit 中&#xff0c;我们不必关心底层的人体骨骼关节点检测算法&#xff0c;也不必自己去调用这些算法&#xff0c;在运行使用 ARBodyTrackingConfiguration 配置的 ARSession 之后&#xff0c;基于摄像头图像的3D人体姿态估计任务也会启动…

LeetCode:292.Nim 游戏

大一开学到现在&#xff0c;我不禁思考一个问题&#xff1a;代码重要吗&#xff1f; 我的答案是&#xff0c;根本不重要&#xff0c;或者说&#xff0c;是次要的。我认为分析问题&#xff0c;和画图是写题的开始&#xff0c;方法的学习&#xff0c;和灵活运用是目的。代码从来…

canvas设置图形各种混合模式,类似photoshop效果

查看专栏目录 canvas实例应用100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…

(6)【Python/机器学习/深度学习】Machine-Learning模型与算法应用—使用Adaboost建模及工作环境下的数据分析整理

目录 一、为什么要使用Adaboost建模? 二、泰坦尼克号分析(工作环境) (插曲)Python可以引入任何图形及图形可视化工具 三、数据分析 四、模型建立 1、RandomForestRegressor预测年龄 2、LogisticRegression建模 引入GridSearchCV 引入RandomizedSearchCV 3、Deci…

《区块链简易速速上手小册》第2章:区块链的工作原理(2024 最新版)

文章目录 2.1 分布式账本技术&#xff08;DLT&#xff09;2.1.1 DLT基础知识2.1.2 主要案例&#xff1a;供应链管理2.1.3 拓展案例 1&#xff1a;数字身份2.1.4 拓展案例 2&#xff1a;投票系统 2.2 加密和安全性2.2.1 加密技术基础2.2.2 主要案例&#xff1a;比特币交易2.2.3 …

【DC渗透系列】DC-2靶场

arp先扫 ┌──(root㉿kali)-[~] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:6b:ed:27, IPv4: 192.168.100.251 Starting arp-scan 1.10.0 with 256 hosts (https://github.com/royhills/arp-scan) 192.168.100.1 00:50:56:c0:00:08 VMware, In…

Macbook 安装金铲铲之战等 IOS 游戏

前言 Macbook 现在可以玩一下 IOS 系统上的游戏啦&#xff0c;以笔者的 M1 Pro 芯片为例 步骤 一、安装 PlayCover 推荐 Sonama 安装 Nightly 版本 官网地址&#xff1a; https://playcover.io/ Nightly: https://nightly.link/playcover/playcover/workflows/2.nightly_re…

SQL 函数(十二)

SQL 函数&#xff08;十二&#xff09; 一、函数分类 1.1 单行函数 单行函数仅对单个行进行运算&#xff0c;并且每行返回一个结果。 常见的函数类型&#xff1a; 字符、数字、日期、转换 1.2 多行函数 多行函数能够操纵成组的行&#xff0c;每个行组给出一个结果&#x…

通过 editplus 批量转换文本编码

有时候需要对文本的编码进行批量转换&#xff0c;文本编辑器 notepad 中的“编码”菜单可以用来转换单个的文档编码&#xff0c;当文档数量多的时候&#xff0c;一个个操作比较繁琐&#xff0c;通过文本编辑器 editplus 软件&#xff0c;可以方便快速地批量修改文本文件的编码&…

帕鲁存档跨云迁服教程

近期一款名为幻兽帕鲁的游戏爆火&#xff0c;以迅雷不及掩耳之势拳打csgo&#xff0c;脚踢dota2&#xff0c;登顶steam同时在线第一名。 由于其独特的个人服务器机制&#xff0c;各大云厂商纷纷响应&#xff0c;腾讯云原价330的4核16G的轻量应用服务器新用户现在最低只要66元一…

GLIP:零样本学习 + 目标检测 + 视觉语言大模型

GLIP 核心思想GLIP 对比 BLIP、BLIP-2、CLIP 主要问题: 如何构建一个能够在不同任务和领域中以零样本或少样本方式无缝迁移的预训练模型&#xff1f;统一的短语定位损失语言意识的深度融合预训练数据类型的结合语义丰富数据的扩展零样本和少样本迁移学习 效果 论文&#xff1a;…

SSL证书的验证过程

HTTPS是工作于SSL层之上的HTTP协议&#xff0c;SSL&#xff08;安全套接层&#xff09;工作于TCP层之上&#xff0c;向应用层提供了两个基本安全服务&#xff1a;认证和保密。SSL有三个子协议&#xff1a;握手协议&#xff0c;记录协议和警报协议。其中握手协议实现服务器与客户…

问题:根据全面推进国防和军队现代化的战略安排,_____把人民军队全面建成世界一流军队。 #经验分享#媒体

问题&#xff1a;根据全面推进国防和军队现代化的战略安排&#xff0c;_____把人民军队全面建成世界一流军队。 A、2020年 B、2035年 C、本世纪中叶 D、2045年 参考答案如图所示 问题&#xff1a;判断题&#xff1a;高处作业传递物件应使用绳索&#xff0c;在确认作业下方…

Qt QGraphicsScene 基于视频的绘图

需求&#xff1a; 基于视频进行 图形的绘制。 方案&#xff1a; 上一篇文章分享了如何将视频实时渲染到QGraphicsScene 系统里&#xff0c;并简单讲述了如何进行绘图&#xff0c;但在实际使用时还是发现了一些技巧&#xff0c;现在总结一下。 Qt 基于海康相机 的视频标绘-CSD…

人类的本性,逃不开党同伐异

近几年以来&#xff0c;不知道大家有没有感受到&#xff0c;网络上越来越充满戾气。 无论哪个网站&#xff0c;只要打开评论区&#xff0c;充斥在眼前的总是一片乌烟瘴气。 一言不合就「对线」&#xff0c;动不动一顶帽子扣过去&#xff0c;说话前先「站队」「找友军」&#xf…

博途PLC限幅器(SCL代码)

PLC限幅器详细介绍,可以参考下面文章: https://rxxw-control.blog.csdn.net/article/details/128701050https://rxxw-control.blog.csdn.net/article/details/128701050三菱PLC限幅器 https://rxxw-control.blog.csdn.net/article/details/135212965

C++入门的基础

幸福比傲慢更容易蒙住人的眼睛。 ——大仲马 C入门 1、属于C的关键字1、1、C从何而来1、2、C关键字(C98) 2、命名空间2、1、命名空间的定义2、2、命名空间使用 3、C输入和输出4、缺省参数4、1、缺省参数概念4、2、缺省参数分类 5、函数重载5、1、函数重载概念 6、引用6、1、引用…