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

【C++单调栈】853. 车队|1678

本文涉及的基础知识点

C++单调栈

LeetCode853. 车队

在一条单行道上,有 n 辆车开往同一目的地。目的地是几英里以外的 target 。
给定两个整数数组 position 和 speed ,长度都是 n ,其中 position[i] 是第 i 辆车的位置, speed[i] 是第 i 辆车的速度(单位是英里/小时)。
一辆车永远不会超过前面的另一辆车,但它可以追上去,并以较慢车的速度在另一辆车旁边行驶。
车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。
即便一辆车在 target 才赶上了一个车队,它们仍然会被视作是同一个车队。
返回到达目的地的车队数量 。
示例 1:
输入:target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出:3
解释:
从 10(速度为 2)和 8(速度为 4)开始的车会组成一个车队,它们在 12 相遇。车队在 target 形成。
从 0(速度为 1)开始的车不会追上其它任何车,所以它自己是一个车队。
从 5(速度为 1) 和 3(速度为 3)开始的车组成一个车队,在 6 相遇。车队以速度 1 移动直到它到达 target。
示例 2:
输入:target = 10, position = [3], speed = [3]
输出:1
解释:
只有一辆车,因此只有一个车队。
示例 3:
输入:target = 100, position = [0,2,4], speed = [4,2,1]
输出:1
解释:
从 0(速度为 4) 和 2(速度为 2)开始的车组成一个车队,在 4 相遇。从 4 开始的车(速度为 1)移动到了 5。
然后,在 4(速度为 2)的车队和在 5(速度为 1)的车成为一个车队,在 6 相遇。车队以速度 1 移动直到它到达 target。
提示:
n == position.length == speed.length
1 <= n <= 105
0 < target <= 106
0 <= position[i] < target
position 中每个值都 不同
0 < speed[i] <= 106

单调栈

性质一:车头速度没边,其它车有可能变化。
性质二:postion[i1] > postion[i2],由于不能超车,则i1从始至终都在i2前面。
性质三:排除i1和i2以外的所有车,如果i2能赶上i1,则在本题一定能加入一个车队。
性质四 ∀ \forall i1,postion[i1] > postion[i2], 排除i1和i2以外的所有车,i2都赶不上i1。则在本题中,i2赶不上任何一两车,即无法加入车队,成为车头。可以用反证法证明:如果加入车队时,车头是i1,车头速度没降。那么除去i1、i2外,i2也能赶上i1。
indexs是postion的下标,postion[indexs[i]] 降序排序。
for(i : indexs) 处理postion[i]和speed[i]。
如果前面有车到达终点需要的时间 >= 当前车需要的时间,则本车会加入车队。
否则是车头。
故只需要记录之前车辆的最晚到达时间,不需要单调栈。
如果需要计算撞的那辆车,则需要用单调栈记录各车时间:
如果后面的车到达时间>=前面车的到达时间,则前面的车永远不再会成为车头,故淘汰之。淘汰后,单调栈降序记录到达时间。处理完当前车队后,如果栈为空则是车头。时间相等无需特殊处理。

代码

核心代码

class Solution {public:int carFleet(int target, vector<int>& position, vector<int>& speed) {const int N = position.size();vector<int> indexs(N);iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return position[i1] >position[i2]; });double maxTime = 0;int ret = 0;for (const auto& i : indexs) {double cur = (target - (double)position[i]) / speed[i];ret += (cur > maxTime);maxTime = max(maxTime, cur);}return ret;}};

单元测试

	int target;vector<int> position, speed;TEST_METHOD(TestMethod1){target = 12, position = { 8,10 }, speed = { 4,2 };auto res = Solution().carFleet(target, position, speed);AssertEx(1, res);}TEST_METHOD(TestMethod11){target = 12, position = { 10,8,0,5,3 }, speed = { 2,4,1,1,3 };auto res = Solution().carFleet(target, position, speed);AssertEx(3, res);}TEST_METHOD(TestMethod12){target = 10, position = { 3 }, speed = { 3 };auto res = Solution().carFleet(target, position, speed);AssertEx(1, res);}TEST_METHOD(TestMethod13){target = 100, position = { 0,2,4 }, speed = { 4,2,1 };auto res = Solution().carFleet(target, position, speed);AssertEx(1, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:

【C++单调栈】853. 车队|1678

本文涉及的基础知识点 C单调栈 LeetCode853. 车队 在一条单行道上&#xff0c;有 n 辆车开往同一目的地。目的地是几英里以外的 target 。 给定两个整数数组 position 和 speed &#xff0c;长度都是 n &#xff0c;其中 position[i] 是第 i 辆车的位置&#xff0c; speed[i…...

第十届文荣奖华丽开幕,郁葱以青春与努力绽放青年演员光芒

10月27日&#xff0c;第十届文荣奖在众人的期待中盛大开启&#xff0c;内地青年女演员郁葱受邀出席&#xff0c;作为国内颇具影响力的影视奖项&#xff0c;文荣奖一直以来都致力于发掘和表彰优秀的影视作品和青年影视人才&#xff0c;为影视行业的发展注入新的活力&#xff0c;…...

CMake 生成器表达式介绍

【写在前面】 生成器表达式在构建系统生成期间进行评估&#xff0c;以生成特定于每个构建配置的信息。它们的形式为 $<...>。例如&#xff1a; target_include_directories(tgt PRIVATE /opt/include/$<CXX_COMPILER_ID>) 这将扩展为 “/opt/include/GNU”、“/opt…...

ubuntu 20.04编译驱动报gcc-12 not found错误

最近在自己安装的Ubuntu 系统上编译自定义驱动&#xff0c;发现无法编译.ko,错误如下&#xff1a; 按照如下操作&#xff0c;发现可以解决&#xff0c;记录下&#xff0c;主要是Ubuntu缺少g-12的包 安装包以后发现可以正常编译...

docker sameersbn/bind dns服务器

1. 安装 #下载docker 镜像 docker pull sameersbn/bind#运行 53端口若被占用会启动失败 docker run --name dns -d --restartalways \ --publish 53:53/tcp \ --publish 53:53/udp \ --publish 10000:10000/tcp \ -v /etc/localtime:/etc/localtime \ -v /data/bind/:/data \…...

错误:无法推送一些引用到 ‘https://gitee.com/chek_kk/python-electron-app.git‘

这个错误提示说明在提交时某个文件的大小超过了 Gitee 仓库的单文件大小限制&#xff08;100MB&#xff09;。你需要从Git 历史中彻底移除这个大文件&#xff0c;否则无法推送到远程仓库。 解决步骤 1. 确认大文件信息 使用以下命令找出超过限制的大文件&#xff1a; git re…...

深度剖析美区代理IP的多元应用与优势

在当今数字时代&#xff0c;代理IP&#xff08;Proxy IP&#xff09;已成为互联网使用中的一项关键技术。尤其在美区&#xff0c;代理IP在数据采集、网络安全及在线隐私保护等领域发挥着越来越重要的作用。本文将深入探讨代理IP的基本概念、应用场景以及它带来的诸多优势&#…...

基于KV260的基础视频链路通路(MIPI+Demosaic+VDMA)

目录 1. 简介 1.1 要点 1.2 背景 1.2.1 Got stuck 1.2.2 Cant be Initialized 2. Overlay 2.1 参考 Overlay 2.1.1 KV260 Base 2.1.2 Pynq-CV-OV5640 2.2 自建 Overlay 2.2.1 IIC IP 2.2.2 MIPI CSI-2 Rx 2.2.3 AXI4-S Subset 2.2.4 Demosaic 2.2.5 Pixel Pack …...

Uni-App-04

主页开发 保存主页数据 <script> import { indexData, base } from /serviceexport default {data() {return {base, //把服务器基础地址变量设置为数据属性carousels:[], //轮播广告条目列表menuItems:[], //当前用户选中的功能菜单列表activities:[], //最新的…...

ElasticSearch分片

本文内容参考了田雪松老师编著的《Elastic Stack应用宝典》 ElasticSearch作为一个搜索引擎&#xff0c;会存储海量的数据。而存储海量的数据&#xff0c;就要解决如何存储的问题&#xff0c;并且保证数据不会丢失&#xff0c;同时还需要保证数据检索的效率&#xff0c;尽可能…...

spring高手之路

以下是一些可以快速入门Spring的方法&#xff1a; 1. 学习基础知识 阅读官方文档&#xff1a;Spring官方文档是最权威的学习资料。它详细介绍了Spring的各个模块、概念和使用方法。从核心模块开始&#xff0c;了解如依赖注入&#xff08;DI&#xff09;和控制反转&#xff08…...

工字钢与H型钢有什么区别?90%的工程师都搞错了!

这里为大家做一个详尽的解答&#xff1a;很多人认为工字钢是国内的叫法&#xff0c;H型钢是国外的叫法&#xff0c;其实这个认知是错误的。H型钢和工字钢从形状上来说是不一样的&#xff0c;见下图&#xff1a; 工字钢 工字钢主要分为普通工字钢、轻型工字钢和宽翼缘工字钢。按…...

10个程序员可以接私活的平台(非常详细)零基础入门到精通,收藏这篇就够了

私活接的好收入不比上班少&#xff0c;一些同学靠接私活月收入也上万甚至几万了。今天老韩来分享一下有哪些接私活的网站和平台&#xff0c;转发收藏以后备用 我们先来聊聊什么样的私活不能接。。 1、没有第三方担保的个人对个人的尽量不要接&#xff0c;双方都没保障&#x…...

小程序云开发CMS新版数据模型讲解,可视化网页管理后台,内容管理对数据库进行增删改查操作,新闻小程序实战学习

一直跟着石头哥学习小程序开发的同学比较清楚cms是什么&#xff0c;cms就是可以进行可视化的管理云开发数据库的网页后台。有了cms我们可以很方便的管理云开发数据库。 但是云开发官方一直改版&#xff0c;所以现在cms功能被整合到了云开发的数据模型里&#xff0c;也就是现在想…...

undertow服务器初始化

springboot整合undertow服务器的源码从老生常谈的createWebServer方法谈起。spring会在生成所有bean后到创建web容器&#xff0c;此时会到容器找到ServletWebServerFactory接口bean&#xff0c;spring会根据引入的框架确定生成的ServletWebServerFactory&#xff0c;我们在mave…...

LeetCode9:回文数

原题地址&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目描述&#xff1a; 给你一个整数 x &#xff0c;如果 x 是一个回文整数&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 回文数 是指正序&#xff08;从左向右&#xff09;和倒序&#xff…...

模板语法(2)

一、循环 在模板中可以用v-for指令来循环数组&#xff0c;对象等。 1. 循环数组 <script setup name"App">import { reactive } from "vue"const books reactive([{title: 三国演义,author: 罗贯中}, {title: 水浒传,author: 施耐庵}, {title: 西…...

从头学PHP之数组输出基本函数

上期我们讲到了数组&#xff0c;数组是个特殊的变量&#xff0c;在程序中的重要程度很高&#xff0c;大部分数据处理的时候会用到这种特殊的变量&#xff0c;那么现在让我们继续深入一下吧。 上期我们打印出了数组的值&#xff0c;用print_r()或者var_dump()这俩函数&#xff0…...

基于SSM+小程序的4S店客户管理系统(汽车2)

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1、项目介绍 4S店客户管理系统主要包括管理员、用户、门店三个权限角色 1、管理员实现了首页、个人中心、用户管理、门店管理、车展管理、汽车品牌管理、新闻头条管理、预约试驾管理、我的收藏管理、…...

ZYNQ AXI_Timer 中断

REVIEW 关于ZYNQ中断&#xff1a; ZYNQ PS_GPIO中断-CSDN博客 ZYNQ AXI_GPIO_INT-CSDN博客 ZYNQ 定时器中断-CSDN博客 在一些应用场景中&#xff0c;可能需要使用到多个定时器&#xff0c;除了选择使用 PS 侧其他定时器外&#xff0c;也可以使用 PL 侧逻辑定时器。 1. 今日摸鱼…...

UE5之5.4 第一人称示例代码阅读2 子弹发射逻辑

TP_WeaponComponent.h 看看头文件 暴露了attach weapon和fire给蓝图 这两个函数意义一看名字吧&#xff0c;就是捡起来枪的时候执行&#xff0c;一个就是发射子弹的时候执行 #pragma once#include "CoreMinimal.h" #include "Components/SkeletalMeshComponen…...

Python 实现日期计算与日历格式化输出(万年历)

目录 一、引言 二、需求分析 三、实现思路 四、代码实现 五、代码分析 六、测试与验证 七、总结与展望 在日常的编程中&#xff0c;我们经常会遇到与日期相关的问题&#xff0c;比如计算两个日期之间的天数差、确定某个特定日期是星期几以及格式化输出日历等。本文将详细…...

10.28.2024刷华为OD C题型

文章目录 HJ9HJ10HJ11HJ13HJ17 HJ9 HJ10 HJ11 HJ13 HJ17...

映射问题的解决办法(mybaitis)

最初我用的是注解来操控数据库&#xff08;注释掉的部分&#xff09; Mapper public interface ThreadMapper {// Select("SELECT * FROM thread LIMIT #{page}, #{size}")List<Thread> getListByPage(Param("page") int page, Param("size&qu…...

关于机器学习方向学习的一些建议(过来人)

以下是关于机器学习方向学习的一些建议&#xff1a; 一、扎实的数学基础 线性代数 线性代数是机器学习的基石。矩阵运算在数据表示、模型参数计算等方面无处不在。例如&#xff0c;在多元线性回归中&#xff0c;我们用矩阵来表示自变量和因变量之间的关系。像最小二乘法求解回…...

【云原生】云原生后端:网络架构详解

目录 引言一、微服务间的通信1.1 通信方式概览1.2 HTTP/REST1.3 gRPC1.4 消息队列1.5 GraphQL 二、API网关2.1 API网关架构示例2.2 API网关实现示例 三、服务发现3.1 服务发现实现示例3.2 服务发现的优势 四、网络安全4.1 网络安全最佳实践4.2 网络安全架构示例 总结参考资料 引…...

期货资管子系统框架设计JS路径及源代码分享

期货资管子系统框架设计JS路径及源代码分享 随着期货资管子系统前端技术的飞速发展&#xff0c;JavaScript&#xff08;JS&#xff09;及其相关框架已成为构建这类系统的重要工具。本文将详细介绍一个期货资管子系统框架的设计思路&#xff0c;并分享部分JS路径及源代码&#…...

【YOLO 系列】基于YOLO的工业自动化轴承缺陷检测系统【python源码+Pyqt5界面+数据集+训练代码】

前言 轴承作为机械设备中的关键部件&#xff0c;其性能直接影响到设备的稳定性和寿命。轴承缺陷的早期检测对于预防设备故障、减少维护成本和提高生产效率至关重要。然而&#xff0c;传统的轴承缺陷检测方法往往依赖于人工检查&#xff0c;这不仅效率低下&#xff0c;而且容易…...

Word中Normal.dotm样式模板文件

Normal.dotm文档 首先将自己电脑中C:\Users\自己电脑用户名\AppData\Roaming\Microsoft\Templates路径下的Normal.dotm文件做备份&#xff0c;在下载本文中的Normal.dotm文件&#xff0c;进行替换&#xff0c;重新打开word即可使用。 字体样式如下&#xff08;可自行修改&#…...

生成式 AI 与向量搜索如何扩大零售运营:巨大潜力尚待挖掘

在竞争日益激烈的零售领域&#xff0c;行业领导者始终在探索革新客户体验和优化运营的新途径&#xff0c;而生成式 AI 和向量搜索在这方面将大有可为。从个性化营销到高效库存管理&#xff0c;二者在零售领域的诸多应用场景中都展现出变革性潜力&#xff0c;已成为保持行业领先…...