首页 > 试题广场 >

加油站

[编程题]加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。

请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。

题目数据可以保证最多有一个答案。

数据范围： $1 \leq n \leq 10^4 \$ ， gas 和 cost 数组中的值满足 $1 \leq val \leq 10^5 \$

示例1

输入

[1,2,3,4,5],[3,4,5,1,2]

只能从下标为 3 的加油站开始完成 （即第四个加油站）

示例2

[0,10],[9,1]

示例3

[2,3,4],[3,4,5]

-1

无论从哪个加油站出发都无法环绕环道一圈

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

贪心数组

难度：

0条回答 44收藏 1681浏览

查看代码

扫一扫，把题目装进口袋