这是一个创建于 805 天前的主题，其中的信息可能已经有所发展或是发生改变。
对于Gas Station - LeetCode，我也想到了跟 NeetCode 同样的算法，但是我不知道怎么证明算法的正确性。
我有以下疑问：
- 为什么 sum(gas) >= sum(cost)就表示一定存在那个 starting index ？
- 怎么证明要找的 starting index 就是 total 一直大于 0 的起点？
第 1 条附言 · 2022-09-07 12:00:21 +08:00
对于疑问2，我现在已经理解了，有需要的人可以看一下Arpan Banejee的comment。
第 2 条附言 · 2022-09-07 16:14:46 +08:00
对于疑问1，我也理解了，以下视频或许对你有帮助。 https://youtu.be/rf66wlb9aNQ?t=482
 |
1
MoYi123 2022-09-07 11:55:58 +08:00
简单说一下具体是怎么样的算法吧, 不然我还要去看个 15 分钟的视频.
|
 |
3
jdz 2022-09-07 15:14:03 +08:00
考虑一个数组[a, b, c, d...] 有正有负, 加起来为正数, 与加油站油量 - 消耗量对应. 所以该数组正数对应 加油站油量大于消耗量.
由于数组为正, 必然存在一个最大子数组和为正, 最大子数组左边(如果存在) 连续的数的和必然为小于等于 0, 同理右边 反证法很容易. 以上想清楚了, 一切就很轻松理解了 核心既是 `最大子数组的左边 连续子数组必然小于等于 0, 右边同理` |
Select Language