当老司机学会了贪心算法 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：当老司机学会了贪心算法

评论礼仪 见这里，违者直接拉黑。

[naruuu-xx]

图像法现在过不了最后两个测试用例了

[labuladong]

@naruuu-xx 感谢指出，已修复，这里是我考虑不周，只要把 minSum = Integer.MAX_VALUE 改为 minSum = 0 就行了

[Feyl]

贪心解法后一个返回值可以直接返回 return start;。
因为start的初始值为0，若初始值为0不满足，后面也不会出现 start == n 的情况。

[tommy-qichang]

不好意思,我有点晕, 这图像法的图是用的哪个case?
比如第一个用例: gas:[1,2,3,4,5]; cost:[3,4,5,1,2]
那么 sum难道不应该是 sum: [0, -2, -4, -6, -3, 0]

[zhongweiLeex]

不好意思,我有点晕, 这图像法的图是用的哪个case? 比如第一个用例: gas:[1,2,3,4,5]; cost:[3,4,5,1,2] 那么 sum难道不应该是 sum: [0, -2, -4, -6, -3, 0]

• 建议仔细看看那个图，是将图整体沿y轴整体上移，将最低的作为起点，并不是说一定要从0出发
• sum其实一直随着start位置不同，而在更新，不一定全是以0为参照的，起点换了，sum不久换了吗，对吧。
• 仔细看看题目，题目中说返回出发时的加油站编号。题目的意思是，让你求一个出发的加油站编号，使得能顺利绕一周。

[tommy-qichang]

不好意思,我有点晕, 这图像法的图是用的哪个case? 比如第一个用例: gas:[1,2,3,4,5]; cost:[3,4,5,1,2] 那么 sum难道不应该是 sum: [0, -2, -4, -6, -3, 0]

• 建议仔细看看那个图，是将图整体沿y轴整体上移，将最低的作为起点，并不是说一定要从0出发
• sum其实一直随着start位置不同，而在更新，不一定全是以0为参照的，起点换了，sum不久换了吗，对吧。
• 仔细看看题目，题目中说返回出发时的加油站编号。题目的意思是，让你求一个出发的加油站编号，使得能顺利绕一周。

我说的是这个图, labuladong描述的很清楚."我们不妨就把0作为起点...."
2. 起点没有换.就算是换也是下一张图的事情.
3. 我理解题目,但是你没有理解我的问题.

[tommy-qichang]

如果例子就是题目中的例子:
gas = [1,2,3,4,5] cost=[3,4,5,1,2]
如果按照文中累加和的代码:

int n = gas.length, sum = 0;
for (int i = 0; i < n; i++) {
    // 计算累加和
    sum += gas[i] - cost[i];
}

那么:
sum :0
i=0: sum = 1-3 = -2
i=1: sum = -2 + 2 - 4 = 0
i=2: sum = 0 + 3-5 = -2
i=3: sum = -2 + 4-1 = 1
i=4: sum = 1 +5 - 2 = 4

怎么算也不会有上面的那个曲线.

[zhongweiLeex]

如果例子就是题目中的例子: gas = [1,2,3,4,5] cost=[3,4,5,1,2] 如果按照文中累加和的代码:

int n = gas.length, sum = 0;
for (int i = 0; i < n; i++) {
    // 计算累加和
    sum += gas[i] - cost[i];
}

那么: sum :0 i=0: sum = 1-3 = -2 i=1: sum = -2 + 2 - 4 = 0 i=2: sum = 0 + 3-5 = -2 i=3: sum = -2 + 4-1 = 1 i=4: sum = 1 +5 - 2 = 4

怎么算也不会有上面的那个曲线.

个人认为 只是举个例子嘛 ， 能让人看懂就行，没必要和题目给出的示例一样。只要意思能表达出来就行
😄

[labuladong]

@tommy-qichang 我随便编的 case，不是题目给的，理解意思就好

[tommy-qichang]

@tommy-qichang 我随便编的 case，不是题目给的，理解意思就好

谢谢解释. 能够理解什么意思,但是如果图文匹配就更好了 :-) 👍

[labuladong]

嗯，有道理，已补上

[7chosen]

什么时候我也能像dong哥一样强😭

[lianchengmingjue]

dong哥好，贪心解法的注释
// 无法从 start 走到 i
我理解应该是
// 无法从 start 走到 i+1个加油站 ?
因为判断if tank<0之前已经加上i到i+1这段路径的加油量gas[i]和损失量-cost[i]了

[labuladong]

@lianchengmingjue 嗯，你说的有道理，很细节👍，我修改下

[ZepinLi]

「贪心解法」如何提现了贪心的思想呢？

[deepbreath373]

check in

[yonggui-yan]

打卡。

[yonggui-yan]

return start == n ? 0 : start;
最后这边，会出现start==n的情况吗？