当前位置: 首页 > news >正文

LeetCode 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], …]

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
解题思路:
本题可以用“扫描线”解决,一般扫描线是用来求解在某点处被多少区间覆盖。
在这里插入图片描述
上图中,灰色竖直线为扫描线,它沿着横轴平移,红、黄、绿三条线表示三个区间。扫描线扫过区间左端点,覆盖扫描线的“区间集合”增加一个区间元素;扫描线扫过区间右端点,覆盖扫描线的“区间集合”减少一个区间元素。覆盖扫描线的“区间集合”个数为0时,则覆盖的集合为空集。h1,h2,h3是区间高度值(height value)。

本题中,对于每一幢建筑物,左右端点影响覆盖扫描线“区间集合”的区间元素个数,即遇到左端点区间元素个数加一,遇到右端点区间元素个数减一。但是
在这里插入图片描述
下图中,以建筑物右端点(下降沿)为例,说明了遇到建筑物右端点,区间集合元素的确减少一,但是区间轮廓可能会发生改变,也可能不发生改变。
在这里插入图片描述

在这里插入图片描述

class Solution {
public:vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {map<int,vector<pair<int,int>>>  Map;//x position -> {height,flag}for(auto building:buildings){Map[building[0]].push_back({building[2],1});Map[building[1]].push_back({building[2],-1});}multiset<int> Set;vector<vector<int>> ans;for(auto& [pos,pairs]:Map){for(auto& [height,flag]:pairs){if(flag==1)Set.insert(height);elseSet.erase(Set.find(height));}int H=Set.empty()? 0:*Set.rbegin();if(ans.empty() || ans.back()[1]!=H)ans.push_back({pos,H});}return ans;  }
};

相关文章:

LeetCode 218. 天际线问题

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度&#xff0c;请返回 由这些建筑物形成的 天际线 。 每个建筑物的几何信息由数组 buildings 表示&#xff0c;其中三元组 buildings[i] [lefti, righti, heighti] 表示&#xf…...

Logstash:使用自定义正则表达式模式

有时 Logstash Grok 没有我们需要的模式。 幸运的是我们有正则表达式库&#xff1a;Oniguruma。在很多时候&#xff0c;如果 Logstash 所提供的正则表达不能满足我们的需求&#xff0c;我们选用定制自己的表达式。 定义 Logstash 是一种服务器端数据处理管道&#xff0c;可同时…...

常见的一致性问题及解决

什么是一致性 一致性问题主要是因为分布式系统中的多个节点之间可能存在网络延迟、故障等原因导致的。具体而言&#xff0c;分布式系统中的数据一致性问题可以分为以下几种类型&#xff1a; 强一致性&#xff1a;指在任何时间点&#xff0c;所有节点中的数据都是一致的。这种…...

vue下载文件

注意请求时加入&#xff1a;responseType: bloburl&#xff1a;写全了&#xff0c;因为前后端端口号不同downloadImage(imgUrl) {let formData new FormData();formData.append(fileName, this.getFilename(imgUrl)); // 用于后端下载文件的路径axios.post(http://localhost:8…...

人人都是数据分析师-数据分析之数据图表可视化(下)

当前的BI报表、运营同学的汇报报告中数据图表大多为 表格、折线图、柱状图和饼图&#xff0c;但是实际上还有很多具有代表性的可视化图表&#xff0c;因此将对常见的可视化图表进行介绍&#xff0c;希望这些图表可视化方法能够更好的提供数据的可用性。 人人都是数据分析师-数…...

考勤、充电,绑身份,你的人员定位系统就缺它了!

我们做人脸识别智能发卡充电柜是要解决什么问题&#xff1f; &#xff08;1&#xff09;工地、港口等场景&#xff0c;人员流动大&#xff0c;管理难 在工地、港口等场景&#xff0c;人员组成通常比较复杂。有来自施工方、客户、各劳务队、各管理层的人员&#xff0c;以及来自…...

RocketMQ水平扩展及负载均衡详解

文章目录 Broker端水平扩展Broker负载均衡commit logProducer负载均衡Consumer负载均衡集群模式广播模式RocketMQ是一个分布式具有高度可扩展性的消息中间件。本文旨在探索在broker端,生产端,以及消费端是如何做到横向扩展以及负载均衡的。 Broker端水平扩展 Broker负载均衡…...

java接口笔记

关键字&#xff1a;interface 定义形式&#xff1a;interface 接口名 { 接口体 } 细节&#xff1a; 1.接口里的方法可以为抽象方法&#xff0c;静态方法&#xff0c;默认方法&#xff08;default 关键字&#xff09; 2.接口里的方法只能是public &#xff0c;可以不用写&a…...

安利安利-向大家推荐一个超级牛的etcd管理工具-EtcdKeeperFyne

etcd介绍 关于etcd的介绍大家可以看下这篇文章 etcd 开源仓库地址&#xff1a;EtcdKeeperFyne EtcdKeeperFyne 今天主要是向大家推荐一款使用起来特别方便的Etcd管理工具 EtcdKeeperFyne&#xff0c;具体运行起来的界面如下&#xff1a; 推荐原因 使用简单安装简单&…...

数字经济系列讲座-数字化平台(商业购物平台)

数字经济系列讲座 文章目录 钱的流向退货成本research questionLiterature review现金流发生在平台内侧平台商业模式转型Modelmodel 假设四种情形标记符利润函数&效用函数&平台效益模型构建利润对比图结论future directions讲座题目 To Adopt or not? The Impacts of…...

python3中collections模块详解

collections模块简介 collections包含了一些特殊的容器&#xff0c;针对Python内置的容器&#xff0c;例如list、dict、set和tuple&#xff0c;提供了另一种选择&#xff1b; namedtuple&#xff0c;可以创建包含名称的tuple&#xff1b; deque&#xff0c;类似于list的容器&a…...

护网面试题2.0

1.CSS和CSRF区别 通俗点讲的话&#xff1a; XSS通过构造恶意语句获取对方cookie&#xff0c; CSRF通过构造恶意链接利用对方cookie&#xff0c;但看不到cookie XSS比CSRF更加容易发生&#xff0c;但CSRF比XSS攻击危害更大 2.XSS原理 XSS&#xff08;Cross-Site Scripting&…...

学习计算机组成原理第1天(计算机发展历程)

计算机发展历程计算机硬件发展计算机软件的发展经典例题计算机硬件发展 计算机的四代变化 1&#xff09;第一代计算机&#xff08;1946-1957年&#xff09;电子管时代。特点&#xff1a;逻辑元件采用电子管&#xff1b;使用机器语言进行编程&#xff1b;主存用延迟线或磁鼓存储…...

二维字符数组与char** 关系 段错误打印

如下为错误&#xff0c;打印断错误。 具体原因参考 http://c.biancheng.net/view/2022.html 二维字符数组与char** 关系 原因&#xff1a; char a[2][20] ; 这是一个二维字符数组。 二维字符数组&#xff0c;这里相当于是两个一维字符串数组。这两个数组在内存的存放位置可以…...

从url输入到页面呈现发生了什么

从url输入到页面呈现发生了什么 1.URL解析 encodeURI / decodeURI 对整个URL的编码&#xff1a;处理空格/中文 let url "http://https://blog.csdn.net/api/ ?lx1&name科比&fromhttp://www.baidu.com/"; console.log(encodeURI(url));encodeURICompone…...

vue之--使用TypeScript

搭配 TypeScript 使用 Vue​ 像 TypeScript 这样的类型系统可以在编译时通过静态分析检测出很多常见错误。这减少了生产环境中的运行时错误&#xff0c;也让我们在重构大型项目的时候更有信心。通过 IDE 中基于类型的自动补全&#xff0c;TypeScript 还改善了开发体验和效率。…...

HDFD 回收站【Trash】机制

一、回收站 Trash 机制开启 HDFS本身是一个文件系统&#xff0c;默认情况下HDFS不开启回收站&#xff0c;数据删除后将被永久删除 添加并修改两个属性值可开启Trash功能 - (core-site.xml) <property> <name>fs.trash.interval</name> <value>1440&…...

【Redis】简介

简介 Redis是一个开源的内存数据结构存储系统&#xff0c;它支持多种数据结构&#xff08;如字符串、哈希、列表、集合、有序集合&#xff09;以及多种功能&#xff08;如事务、发布/订阅、Lua脚本执行等&#xff09;。Redis还提供了持久化功能&#xff0c;可以将数据存储到磁…...

【Go进阶】Goroutine 实现原理

目录 1、GMP模型 2、Goroutine调度策略 队列轮转 系统调用 工作量窃取...

TypeScript学习笔记之二(高级类型)

文章目录一、TypeScript高级类型1.1 class类1.2 class继承1.3 class类成员可见性1.4 readonly1.5 类型兼容性1.5.1 对象之间的类型兼容性1.5.2 接口之间类型兼容性1.5.3 函数之间类型兼容性1.6 交叉类型1.7 交叉类型(&)和继承(extends)的对比二、泛型2.1 泛型约束--指定更具…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...