From
Leetcode
Status
AC
Date
Mar 25, 2024
Tags
贪心算法
Difficulty
中等
题面
在一条环路上有
n
个加油站,其中第 i
个加油站有汽油 gas[i]
升。你有一辆油箱容量无限的的汽车,从第
i
个加油站开往第 i+1
个加油站需要消耗汽油 cost[i]
升。你从其中的一个加油站出发,开始时油箱为空。给定两个整数数组
gas
和 cost
,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1
。如果存在解,则 保证 它是 唯一 的。示例 1:
示例 2:
提示:
gas.length == n
cost.length == n
1 <= n <= 10
5
0 <= gas[i], cost[i] <= 10
4
思路
totSum ≥ 0 一定有解
一旦[0,i] 区间和为负数,起始位置就可以是i+1