134. 加油站
| 2024-3-25
0  |  阅读时长 0 分钟
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 <= 105
  • 0 <= gas[i], cost[i] <= 104
 

思路

totSum ≥ 0 一定有解
一旦[0,i] 区间和为负数,起始位置就可以是i+1
 

题解

Loading...
目录