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

【反悔堆】力扣1642. 可以到达的最远建筑

给你一个整数数组 heights ,表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程,不断向后面的建筑物移动,期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1(下标 从 0 开始 )时:

如果当前建筑物的高度 大于或等于 下一建筑物的高度,则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度,您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块,返回你可以到达的最远建筑物的下标(下标 从 0 开始 )。

示例 1:
输入:heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出:4
解释:从建筑物 0 出发,你可以按此方案完成旅程:

  • 不使用砖块或梯子到达建筑物 1 ,因为 4 >= 2
  • 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子,因为 2 < 7
  • 不使用砖块或梯子到达建筑物 3 ,因为 7 >= 6
  • 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子,因为 6 < 9
    无法越过建筑物 4 ,因为没有更多砖块或梯子。

示例 2:
输入:heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出:7

示例 3:
输入:heights = [14,3,19,3], bricks = 17, ladders = 0
输出:3

在这里插入图片描述

反悔堆

class Solution {
public:int furthestBuilding(vector<int>& heights, int bricks, int ladders) {int n = heights.size();priority_queue<int, vector<int>, greater<int>> q;int sumH = 0;for(int i = 1; i < n; i++){int deltaH = heights[i] - heights[i-1];if(deltaH > 0){q.push(deltaH);if(q.size() > ladders){sumH += q.top();q.pop();}if(sumH > bricks){return i - 1;}}}return n - 1;}
};

为了达到更远的距离,所以我们梯子尽量要用在高差比较大的楼之间。我们定义一个最小堆q,用来表示使用梯子的高度分别是哪些。

我们模拟从建筑1向建筑n移动,当出现前面建筑更高的时候,就将deltaH放到最小堆q中,如果最小堆里元素数量大于梯子数量,那么我们就弹出最小高差来使用砖块,以保证最高差都是用梯子。

我们用sumH来记录需要砖块的个数是多少,当sumH大于我们所拥有的砖块个数的时候,说明无法到达更远距离,返回i-1。我们最远可以到达n-1.

相关文章:

【反悔堆】力扣1642. 可以到达的最远建筑

给你一个整数数组 heights &#xff0c;表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。 你从建筑物 0 开始旅程&#xff0c;不断向后面的建筑物移动&#xff0c;期间可能会用到砖块或梯子。 当从建筑物 i 移动到建筑物 i1&#xff08;下标 从 0 开始 &#xff09;…...

关于使用Mybatis-plus的TableNameHandler动态表名处理器实现分表业务的详细介绍

引言 随着互联网应用的快速发展&#xff0c;数据量呈爆炸式增长。传统的单表设计在面对海量数据时显得力不从心&#xff0c;容易出现性能瓶颈、查询效率低下等问题。为了提高数据库的扩展性和响应速度&#xff0c;分表&#xff08;Sharding&#xff09;成为了一种常见的解决方案…...

docker 安装 redis 详解

在平常的开发工作中&#xff0c;我们经常会用到 redis&#xff0c;那么 docker 下应该如何安装 redis 呢&#xff1f;简单来说&#xff1a;第一步&#xff1a;拉取redis镜像&#xff1b;第二步&#xff1a;设置 redis.conf 配置文件&#xff1b;第三步&#xff1a;编写 docker-…...

56. 合并区间

【题目】&#xff1a;56. 合并区间 class Solution { public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 按照左端点排序sort(intervals.begin(), intervals.end(), [&](vector<int> lhs, vector<int> rhs)…...

BOM对象location与数组操作结合——查询串提取案例

BOM对象location与数组操作结合——查询串提取案例 前置知识 1. Location 对象 Location 对象是 JavaScript 提供的内置对象之一&#xff0c;它表示当前窗口或框架的 URL&#xff0c;并允许你通过它操作或获取 URL 的信息。可以通过 window.location 访问。 主要属性&#…...

Jetson Orin Nano Super之 onnxruntime 编译安装

Jetson Orin Nano Super之 onnxruntime 编译安装 1. 源由2. 步骤步骤一&#xff1a;安装3.26 cmake步骤二&#xff1a;下载代码步骤三&#xff1a;编译代码步骤四&#xff1a;找到安装包步骤五&#xff1a;安装whl包 3. 注意4. 参考资料 1. 源由 Build onnxruntime 1.19.2 fai…...

开发环境搭建-3:配置 nodejs 开发环境 (fnm+ node + pnpm)

在 WSL 环境中配置&#xff1a;WSL2 (2.3.26.0) Oracle Linux 8.7 官方镜像 node 官网&#xff1a;https://nodejs.org/zh-cn/download 点击【下载】&#xff0c;选择想要的 node 版本、操作系统、node 版本管理器、npm包管理器 根据下面代码提示依次执行对应代码即可 基本概…...

[SWPUCTF 2022 新生赛]js_sign

题目 查看页面源代码 <!DOCTYPE html> <html> <head><meta charset"utf-8"><style>body {background-color: rgb(255, 255, 255);}</style> </head> <body><input id"flag" /><button>Check…...

农业信息化的基本框架

农业信息化的主要研究内容 基于作物模型的相关研究 作物生长模拟模型以及模型评价、模型的应用作物模型应用&#xff0c;包括&#xff1a;作物生态系统过程、生产管理措施、区域作物产量评估与气候变化对产量影响预测、基于作物模型的决策支持系统 数据挖掘、知识工程及应用、管…...

OpenAI的真正对手?DeepSeek-R1如何用强化学习重构LLM能力边界——DeepSeek-R1论文精读

2025年1月20日&#xff0c;DeepSeek-R1 发布&#xff0c;并同步开源模型权重。截至目前&#xff0c;DeepSeek 发布的 iOS 应用甚至超越了 ChatGPT 的官方应用&#xff0c;直接登顶 AppStore。 DeepSeek-R1 一经发布&#xff0c;各种资讯已经铺天盖地&#xff0c;那就让我们一起…...

Vue 3 中的父子组件传值:详细示例与解析

在 Vue 3 中&#xff0c;父子组件之间的数据传递是一个常见的需求。父组件可以通过 props 将数据传递给子组件&#xff0c;而子组件可以通过 defineProps 接收这些数据。本文将详细介绍父子组件传值的使用方法&#xff0c;并通过优化后的代码示例演示如何实现。 1. 父子组件传值…...

回顾2024,展望2025

项目 LMD performance phase2 今年修修补补&#xff0c;设计和做了很多item&#xff0c;有时候自己都数不清做了什么大大小小的item&#xff0c;但是for LMD performance phase2的go-live确实是最大也是最难的了&#xff0c;无论什么系统&#xff0c;只要用的人多了&#xff…...

【Python实现机器遗忘算法】复现2021年顶会 AAAI算法Amnesiac Unlearning

【Python实现机器遗忘算法】复现2021年顶会 AAAI算法Amnesiac Unlearning 1 算法原理 论文&#xff1a;Graves, L., Nagisetty, V., & Ganesh, V. (2021). Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 115…...

Vue 3 30天精进之旅:Day 03 - Vue实例

引言 在前两天的学习中&#xff0c;我们成功搭建了Vue.js的开发环境&#xff0c;并创建了我们的第一个Vue项目。今天&#xff0c;我们将深入了解Vue的核心概念之一——Vue实例。通过学习Vue实例&#xff0c;你将理解Vue的基础架构&#xff0c;掌握数据绑定、模板语法和指令的使…...

【ArcGIS微课1000例】0141:提取多波段影像中的单个波段

文章目录 一、波段提取函数二、加载单波段导出问题描述:如下图所示,img格式的时序NDVI数据有24个波段。现在需要提取某一个波段,该怎样操作? 一、波段提取函数 首先加载多波段数据。点击【窗口】→【影像分析】。 选择需要处理的多波段影像,点击下方的【添加函数】。 在多…...

【第九天】零基础入门刷题Python-算法篇-数据结构与算法的介绍-六种常见的图论算法(持续更新)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、Python数据结构与算法的详细介绍1.Python中的常用的图论算法2. 图论算法3.详细的图论算法1&#xff09;深度优先搜索&#xff08;DFS&#xff09;2&#xf…...

落地 轮廓匹配

个人理解为将一幅不规则的图形&#xff0c;通过最轮廓发现&#xff0c;最大轮廓匹配来确定图像的位置&#xff0c;再通过pt将不规则的图像放在规定的矩形里面&#xff0c;在通过透视变换将不规则的图形放进规则的图像中。 1. findHomography 函数 • Mat h findHomography(s…...

【漫话机器学习系列】064.梯度下降小口诀(Gradient Descent rule of thume)

梯度下降小口诀 为了帮助记忆梯度下降的核心原理和关键注意事项&#xff0c;可以用以下简单口诀来总结&#xff1a; 1. 基本原理 损失递减&#xff0c;梯度为引&#xff1a;目标是让损失函数减少&#xff0c;依靠梯度指引方向。负梯度&#xff0c;反向最短&#xff1a;沿着负…...

JAVA(SpringBoot)集成Kafka实现消息发送和接收。

SpringBoot集成Kafka实现消息发送和接收。 一、Kafka 简介二、Kafka 功能三、POM依赖四、配置文件五、生产者六、消费者 君子之学贵一&#xff0c;一则明&#xff0c;明则有功。 一、Kafka 简介 Kafka 是由 Apache 软件基金会开发的一个开源流处理平台&#xff0c;最初由 Link…...

AI刷题-蛋糕工厂产能规划、优质章节的连续选择

挑两个简单的写写 目录 一、蛋糕工厂产能规划 问题描述 输入格式 输出格式 解题思路&#xff1a; 问题理解 数据结构选择 算法步骤 关键点 最终代码&#xff1a; 运行结果&#xff1a;​编辑 二、优质章节的连续选择 问题描述 输入格式 输出格式 解题思路&a…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...