当前位置: 首页 > 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…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...