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

LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑

LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑

  • 题目描述
  • 示例
    • 示例1:
    • 示例2:
  • 思路
  • 代码

题目描述

给你一个下标从 0 开始的正整数数组 heights ,其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ,且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ,那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ,其中 queries[i] = [ai, bi] 。第 i 个查询中,Alice 在建筑 ai ,Bob 在建筑 bi

请你能返回一个数组 ans ,其中 ans[i] 是第 i 个查询中,Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ,Alice 和 Bob 不能相遇,令 ans[i] 为 -1 。

示例

示例1:

输入:heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出:[2,5,-1,5,2]
解释:第一个查询中,Alice 和 Bob 可以移动到建筑 2 ,因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Alice 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中,Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。

示例2:

输入:heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出:[7,6,-1,4,6]
解释:第一个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[0] < heights[7] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 6 ,因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Bob 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 4 ,因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。

思路

采用最小堆

算法涉及到三个位置,假定 a≤b,按照从左到右的顺序,它们分别是:

  1. a:回答询问时,用其高度 heights[a] 和当前高度 heights[i] 比大小,如果heights[a]<heights[i] 则找到答案。
  2. b:决定了在什么位置把询问加入堆中。注意在遍历到位置 b之前是不能入堆的。在遍历到位置 b 时入堆,这样后续只需要比较 heights[a]<heights[i],如果成立,就间接地说明heights[b]<heights[i] 也成立。并且,由于我们是从左往右遍历 heights 的,当前下标 i 就是 Alice 和Bob 可以相遇的最左边建筑的下标。
  3. 回答询问的位置 i。如果堆顶 heights[a] 小于当前位置的高度heights[i],则回答堆顶询问,并弹出堆顶。

代码

class Solution:def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:ans = [-1] * len(queries)qs = [[] for _ in heights]for i,(a,b) in enumerate(queries):if a > b:a,b = b,aif a == b or heights[a]<heights[b]:ans[i] = belse:qs[b].append((heights[a],i))h = []for i,x in enumerate(heights):while h and h[0][0] < x:ans[heappop(h)[1]] = ifor q in qs[i]:heappush(h,q)return ans

相关文章:

LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑

LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑 题目描述示例示例1&#xff1a;示例2&#xff1a; 思路代码 题目描述 给你一个下标从 0 开始的正整数数组 heights &#xff0c;其中 heights[i] 表示第 i 栋建筑的高度。 如果一个人在建筑 i &#xff0c;且存在 i &…...

unity 判断平台

原文链接 Unity中判断平台的方法 Unity提供了一些方法来判断当前运行的平台&#xff0c;其中包括了判断是否为i0S平台。以下是几种常用的方法1.Application.platform Applicaion,platom 是Unity中的一个枚举类型&#xff0c;用于表示当前运行的平台。可以通过比较 Apication,p…...

PyCharm找不到Python了咋办

Python发生了重装的&#xff0c;且新的路径和原有路径不同&#xff0c;就会出现如下的错误&#xff1a; 解决办法&#xff1a; 点开PyCharm菜单的File/Setting 然后&#xff1a; 有上图的提示&#xff0c;说明需要将原来的venv进行清空。 如此操作之后&#xff0c;原来的红色…...

BRC-100 协议

BRC-100 协议 BRC-100 是一种基于序数理论的可扩展的去中心化计算协议。 BRC-100 协议会以下面的方式定义。未来所有的 BRC-100 协议栈都应该使用类似的规范来定义。 1. 摘要 BRC-100 协议是一种基于序数理论的可扩展的去中心化计算协议。 2. 抽象 BRC-100 协议本质上描述…...

茶余饭后(六)

年少成长的时候&#xff0c;多遇到一些所谓的“坏人”&#xff0c;“烂人”&#xff0c;其实是好的&#xff0c;因为这些人让你见识到了人性最丑陋的一面&#xff0c;他们让你磨炼了心性&#xff0c;在以后遇到难处理的人或事的时候&#xff0c;能够有一定的心理承受能力。遇见…...

秋招复习笔记——八股文部分:网络IP

终于来到了网络的最后一篇&#xff0c;继续加油&#xff01; IP 知识全家桶 IP 基本认识 IP 在 TCP/IP 参考模型中处于第三层&#xff0c;也就是网络层。 网络层的主要作用是&#xff1a;实现主机与主机之间的通信&#xff0c;也叫点对点&#xff08;end to end&#xff09…...

量化投资基础(四)之AR、MA、ARMA与ARIMA模型

点赞、关注&#xff0c;养成良好习惯 Life is short, U need Python 量化投资基础系列&#xff0c;不断更新中 1 引言 时间序列经典模型主要有: 自回归模型&#xff08;Auto Regressive&#xff0c;AR&#xff09;移动回归模型&#xff08;Moving Average&#xff0c;MA&…...

LVS(Linux Virtual Server)详解

LVS&#xff08;Linux Virtual Server&#xff09;是一个用于负载均衡的开源软件项目&#xff0c;旨在通过集群技术实现高性能、高可用的服务器系统。它运行在Linux操作系统上&#xff0c;并且可以利用内核级的资源来提高性能和稳定性。 思维导图 LVS的工作原理 LVS主要基于Ne…...

uniapp版本更新除了plus.runtime.getProperty的解决办法

以下是展示图 带尺寸的图片: 首先把以下代码放到想要更新弹出的页面 //template部分<uni-popup ref"popup" background-color"#fff"><versionUp handleCloseVersion"closeVersion"></versionUp></uni-popup>//script…...

MySQL笔记-基础篇(二):多表查询

​ 博客主页: 南来_北往 系列专栏&#xff1a;Spring Boot实战 前言 MySQL的多表查询是一项非常实用的数据库操作技术&#xff0c;它能够通过关联不同表中的数据来提供更加丰富和准确的信息。在实际应用中&#xff0c;数据通常不是孤立存在的&#xff0c;而是分布在多个…...

备战秋招60天算法挑战,Day15

题目链接&#xff1a; https://leetcode.cn/problems/minimum-window-substring/ 视频题解&#xff1a; https://www.bilibili.com/video/BV1sJ4m1g727/ LeetCode 76. 最小覆盖子串 题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s …...

【学习笔记】Matlab和python双语言的学习(整数规划和0-1规划)

文章目录 前言一、整数规划和0-1规划二、典型示例1.背包问题2.指派问题 三、代码实现----Matlab1.Matlab 的 intlinprog 函数2.Matlab 代码背包问题指派问题 四、代码实现----python背包问题指派问题 总结 前言 通过模型算法&#xff0c;熟练对Matlab和python的应用。 学习视频…...

【连续4届EI检索,SPIE 出版】第五届信号处理与计算机科学国际学术会议(SPCS 2024,8月23-25)

第五届信号处理与计算机科学国际学术会议&#xff08;SPCS 2024) 将于2024年8月23-25日在中国哈尔滨举行。会议主要围绕信号处理与计算机科学等研究领域展开讨论。 会议旨在为从事信号处理与计算机科学研究的专家学者、工程技术人员、技术研发人员提供一个共享科研成果和前沿技…...

Vue屏蔽Console.Log打印信息

Vue屏蔽打印信息 安装 npm install uglifyjs-webpack-plugin --save-dev 在vue.config.js文件或者webpack.prod.conf.js中配置 vue.config中 const UglifyJsPlugin require(uglifyjs-webpack-plugin) // 屏蔽打印数据 module.exports {optimization: {minimizer: [new Ugl…...

数据结构之《二叉树》(下)

在二叉树(中)了解了堆的相关概念后还实现了堆&#xff0c;并且还实现了堆排序&#xff0c;以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构&#xff0c;会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树&#xff0c;接下来就开始本篇的学习吧&…...

用Python打造精彩动画与视频,9.3 项目案例分享与反思

第九章&#xff1a;综合项目 9.3 项目案例分享与反思 在本节中&#xff0c;我们将分享几个成功的项目案例&#xff0c;并进行反思总结。这些案例将展示如何将前面所学的Python技术运用于实际项目中&#xff0c;同时我们将讨论项目中的挑战和解决方案&#xff0c;以及从中得到…...

分布式主键 详解

文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题 问题出现 使用ShardingSphere框架自带的雪花算法生成分布式主…...

synchronzed为什么要升级为重量级锁,轻量级锁不好吗?

轻量级锁和重量级锁各有其适用场景和优缺点。轻量级锁旨在减少在无竞争情况下的同步开销&#xff0c;而重量级锁则在竞争激烈的情况下确保线程的同步。以下是为什么在某些情况下需要将轻量级锁升级为重量级锁的原因&#xff0c;以及轻量级锁的不足之处&#xff1a; 为什么需要…...

.NET 项目中发送电子邮件异步处理和错误机制的解决方案

在 .NET 中处理电子邮件&#xff0c;可以使用多种技术和库来实现高效的电子邮件发送、接收和管理。以下是一些常见的解决方案和最佳实践&#xff1a; 目录 1. 使用 SMTP 发送电子邮件 2. 使用 IMAP/POP3 接收电子邮件 3. 异步处理电子邮件 4. 处理大型邮件队列 5. 错误处…...

如何在银河麒麟操作系统上搭建 Electron (含 Electron 打包指南)

本次教程所用版本 Eletron版本&#xff1a;31.3.1 Electron-packager版本&#xff1a;17.1.2 VScode版本&#xff1a;1.92.0 Node版本&#xff1a;18.19.0 npm版本&#xff1a;10.2.3 前言&#xff1a; 随着跨平台应用开发的需求日益增长&#xff0c;Electron 和 Qt 成为…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...