对于Gas Station - LeetCode,我也想到了跟 NeetCode 同样的算法,但是我不知道怎么证明算法的正确性。
我有以下疑问:
对于疑问2,我现在已经理解了,有需要的人可以看一下Arpan Banejee的comment。
对于疑问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, 右边同理` |