LeetCode 134. 加油站(函数图像法 / 贪心)
题目:
链接:LeetCode 134. 加油站
难度:中等
在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
给定两个整数数组 gas 和 cost ,如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。
提示:
- gas.length == n
- cost.length == n
- 1 <= n <= 105
- 0 <= gas[i], cost[i] <= 104
方法一:
函数图像法:

sum 代表路途中油箱的油量,如果把这个「最低点」作为起点,即把这个点作为坐标轴原点,就相当于把图像「最大限度」向上平移了:

如果经过平移后图像全部在 x 轴以上,就说明可以行使一周。
代码一:
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int minsum = 0, minpos = 0; //函数最低点的值,函数最低点的坐标(出发站编号)int sum = 0;for(int i = 0; i < n; i++){sum += gas[i] - cost[i];if(sum < minsum) {minsum = sum;minpos = i + 1;}}if(sum < 0) return -1;return minpos % n;}
};
时间复杂度O(n),空间复杂度O(1)。
方法二:
贪心解法:
用贪心思路解决这道题的关键在于以下这个结论:
如果选择站点i作为起点「恰好」无法走到站点j,那么i和j中间的任意站点k都不可能作为起点。
比如说,如果从站点1出发,走到站点5时油箱中的油量「恰好」减到了负数,那么说明站点1「恰好」无法到达站点5;那么你从站点2,3,4任意一个站点出发都无法到达5,因为到达站点5时油箱的油量也必然被减到负数。
如何证明这个结论?
假设sum记录当前油箱中的油量,如果从站点i出发(sum = 0),走到j时恰好出现sum < 0的情况,那说明走到i, j之间的任意站点k时都满足sum > 0,对吧。
如果把k作为起点的话,相当于在站点k时sum = 0,那走到j时必然有sum < 0,也就是说k肯定不能是起点。
拜托,从i出发走到k好歹sum > 0,都无法达到j,现在你还让sum = 0了,那更不可能走到j了对吧。
综上,这个结论就被证明了。
回想一下我们开头说的暴力解法是怎么做的?
如果我发现从i出发无法走到j,那么显然i不可能是起点。
现在,我们发现了一个新规律,可以推导出什么?
如果我发现从i出发无法走到j,那么i以及i, j之间的所有站点都不可能作为起点。
看到冗余计算了吗?看到优化的点了吗?
这就是贪心思路的本质,如果找不到重复计算,那就通过问题中一些隐藏较深的规律,来减少冗余计算。
代码二:
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n;){int sum = 0;bool flag = true; //以i为出发站时能否环行一周for(int j = i; j < i + n; j++){sum += gas[j % n] - cost[j % n]; //行至第j+1个加油站时,油箱内的油量if(sum < 0) {if(j + 1 >= n) return -1; //全部出发点已遍历完,未找到可行解i = (j + 1) % n; //无法从第i站到第j+1站,则从中间任意一站都无法到第j+1站。那么以第j+1站为出发站继续检查flag = false;break;}}if(flag) return i; //以第i站为出发站可以走完一周,返回i}return -1;}
};
时间复杂度O(n),空间复杂度O(1)。
相关文章:
LeetCode 134. 加油站(函数图像法 / 贪心)
题目: 链接:LeetCode 134. 加油站 难度:中等 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中…...
王道计算机组成原理课代表 - 考研计算机 第三章 存储系统 究极精华总结笔记
本篇博客是考研期间学习王道课程 传送门 的笔记,以及一整年里对 计算机组成 知识点的理解的总结。希望对新一届的计算机考研人提供帮助!!! 关于对 存储系统 章节知识点总结的十分全面,涵括了《计算机组成原理》课程里…...
Flask-mock接口数据流程
背景:由于在开发过程中,会遇到以下的痛点 1.服务端接口提测延期,具体接口逻辑未完成实现,接口未能正常调通,导致客户端提测停滞; 2.因为前期已在技术评审上已与客户端开发定好接口字段,客户端比…...
springboot项目配置序列化,反序列化器
介绍本文介绍在项目中时间类型、枚举类型的序列化和反序列化自定义的处理类,也可以使用注解。建议枚举都实现一个统一的接口,方便处理。我这定义了一个Dict接口。枚举类型注解处理这种方式比较灵活,可以让枚举按照自己的方式序列化࿰…...
c++11 标准模板(STL)(std::unordered_map)(九)
定义于头文件 <unordered_map> template< class Key, class T, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator< std::pair<const Key, T> > > class unordered…...
Seay代码审计工具
一、简介Seay是基于C#语言开发的一款针对PHP代码安全性审计的系统,主要运行于Windows系统上。这款软件能够发现SQL注入、代码执行、命令执行、文件包含、文件上传、绕过转义防护、拒绝服务、XSS跨站、信息泄露、任意URL跳转等漏洞,基本上覆盖常见PHP漏洞…...
界面开发(4)--- PyQt5实现打开图像及视频播放功能
PyQt5创建打开图像及播放视频页面 上篇文章主要介绍了如何实现登录界面的账号密码注册及登录功能,还简单介绍了有关数据库的连接方法。这篇文章我们介绍一下如何在设计的页面中打开本地的图像,以及实现视频播放功能。 实现打开图像功能 为了便于记录实…...
核心系统国产平台迁移验证
核心系统国产平台迁移验证 摘要:信息技术应用创新,旨在实现信息技术领域的自主可控,保障国家信息安全。金融领域又是关系国家经济命脉的行业,而对核心交易系统的信息技术应用创新是交易所未来将要面临的重大挑战。为了推进国产化进…...
【数据结构之二叉树】——二叉树的概念及结构,特殊的二叉树和二叉树性质
文章目录一、二叉树的概念及结构1.概念2.现实中的二叉树3. 特殊的二叉树:3.二叉树的性质二、二叉树练习题总结一、二叉树的概念及结构 1.概念 一棵二叉树是结点的一个有限集合,该集合: 或者为空由一个根节点加上两棵别称为左子树和右子树的二叉树组成…...
Android学习之帧动画和视图动画
帧动画 帧动画中的每一帧其实都是一张图片,将许多图片连起来播放,就形成了帧动画。 在drawable目录下新建frmae_animation文件,在这个文件中定义了帧动画的每一帧要显示的图片,播放时,按从上到下显示。 <?xml v…...
vue2和vue3的区别
这周呢主要就是整理整理学的东西,不然看的也记不住,把这些学的东西做成笔记,感觉会清楚许多,这次就把vue2和vue3的区别总结一下,明天要考四级,嗐,本来想着复习四级,结果只写了一两套…...
【你不知道的事】JavaScript 中用一种更先进的方式进行深拷贝:structuredClone
你是否知道,JavaScript中有一种原生的方法来做对象的深拷贝? 本文我们要介绍的是 structuredClone 函数,它是内置在 JavaScript 运行时中的: const calendarEvent {title: "Builder.io Conf",date: new Date(123),attendees: ["Steve…...
XE开发Linux应用(二)-Webservice
新建一个工程。选择如图。继续输入服务名然后就生成对应的单元。增加linux 平台。完善对应的单元代码{ Invokable implementation File for Txaliontest which implements Ixaliontest }unit xaliontestImpl;interfaceuses Soap.InvokeRegistry, System.Types, Soap.XSBuiltIns…...
kubernetes实战与源码学习
1.1 关于Kubernetes的介绍与核心对象概念 关于Kubernetes的介绍与核心对象概念-阿里云开发者社区 k8s架构 核心对象 使用kubeadm10分钟部署k8集群 使用 KuboardSpray 安装kubernetes_v1.23.1 | Kuboard k8s-上部署第一个应用程序 Deployment基本概念 给应用添加service&a…...
CNCF x Alibaba云原生技术公开课 第八章 应用配置管理
Pod配置管理分类 可变配置就用 ConfigMap;敏感信息是用 Secret;身份认证是用 ServiceAccount;资源配置是用 Resources;安全管控是用 SecurityContext;前置校验是用 InitContainers。 1、ConfigMap 概念:…...
YUV实践记录
文章目录YUV基础介绍:不同采样YUV格式的区别为什么要使用YUV格式呢?YUV的存储方式Android中的YUV_420_888附录:YUV基础介绍: YUV在做手机图像或者视频处理的时候会经常用到的一个格式,用此文来记录YUV相关介绍…...
【题解】百度2020校招Web前端工程师笔试卷(第一批):单选题、多选题
题目来源 若有错误请指正! 单选 1 分页存储管理将进程的逻辑地址空间分成若干个页,并为各页加以编号,从0开始,若某一计算机主存按字节编址,逻辑地址和物理地址都是32位,页表项大小为4字节,若…...
探索云原生技术之容器编排引擎-kubeadm安装kubernetes1.21.10(新版:针对高版本内核)
❤️作者简介:2022新星计划第三季云原生与云计算赛道Top5🏅、华为云享专家🏅、云原生领域潜力新星🏅 💛博客首页:C站个人主页🌞 💗作者目的:如有错误请指正,将…...
2023广西自治区职业技能大赛“网络安全” 项目比赛任务书
2023广西自治区职业技能大赛“网络安全” 项目比赛任务书2023广西自治区职业技能大赛“网络安全” 项目比赛任务书A模块基础设施设置/安全加固(200分)A-1:登录安全加固(Windows, Linux)A-2:Nginx安全策略&a…...
Reactor模式
Reactor是一种设计模式,可以用于构建高并发的网络服务器。 Reactor模式的好处在于:可以在一个或多个reactor线程使用多路复用技术去管理所有网络连接连接建立、IO请求,保证工作线程不被IO阻塞。 前置知识:IO多路复用技术 1. 传统网…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
