• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LeetCode-加油站

开发技术 开发技术 1周前 (04-08) 4次浏览

LeetCode-加油站

 

 

 LeetCode-加油站

 

 

 最近刷题的时候遇到一个有意思的解法,解决思路不同常法,且拥有不错的性能表现。下面是分析过程:

 

以该题为例:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
下图的黑色折线图总油量剩余值,若要满足题目的要求:跑完全程再回到起点,总油量剩余值的任意部分都需要在X轴以上,且跑到终点时:总剩余汽油量 >= 0

为了让黑色折线图任意部分都在 X 轴以上,我们需要向上移动黑色折线图,直到所有点都在X轴或X轴以上。此时,处在X轴的点即为出发点。即黑色折线图的最低值的位置:index = 3。

LeetCode-加油站

柱状图
绿色:可添加的汽油 gas[i]
橙色:消耗的汽油 cose[i]

折线图:
虚线(蓝色):当前加油站的可用值
实线(黑色):从0开始的总剩余汽油量

执行用时: 0 ms, 在所有 java 提交中击败了 100.00% 的用户
内存消耗: 37.2 MB, 在所有 java 提交中击败了 72.07% 的用户

 

 1 public int canCompleteCircuit(int[] gas, int[] cost) {
 2     int len = gas.length;
 3     int spare = 0;
 4     int minSpare = Integer.MAX_VALUE;
 5     int minIndex = 0;
 6 
 7     for (int i = 0; i < len; i++) {
 8         spare += gas[i] - cost[i];
 9         if (spare < minSpare) {
10             minSpare = spare;
11             minIndex = i;
12         }
13     }
14 
15     return spare < 0 ? -1 : (minIndex + 1) % len;
16 }

使用语言:java

时间复杂度:O(N)
空间复杂度:O(1)

需要补充说明的是,许多人认为

index=3,从第三个点出发,gas[ 2 ] = 3, cost [ 2 ] = 5,显然错误

实际上是误解了图中各点的含义,尤其是索引号的含义。首先整张图是从0点(i=0,即第一个站)出发的到达各个点时剩余油量图,X轴对应的是到达的各个点。i=0对应的是第一个站,即gas[0]这个站,刚到时即没有加油也没有耗油,为0;i=1对应的是第二个站,即gas[1]这个站,刚到时,经历了0+gas[0]-cost[0],此时剩余的油量为-2;实际上

index=3,对应的是第四个站,也就是从第四个站出发,gas[ 3 ] = 4, cost [ 3 ] = 1,起步成功

这个图是从0点(i=0,即第一个站)出发的折线图,那么改变出发点时,这个图会怎么变化呢?实际去画,会发现整体折线图的形状是没有变的,改变的是y值,相当于将折线图在Y轴方向上上下平移。那么,当最小点落在X轴上时(也就是使得最小点y=0时),整体折线在X轴上方,y值恒大于等于0,也就是剩余油量一直不为负,可以绕行一圈。对于本例,也就是使得i=3时,y=0。此时,意味着从i=3,第四个站出发,到此站时即没有加油也没有耗油,剩余油量为0。

正常解题思路往往是用贪心算法,然后优化贪心算法减少遍历的次数以提高性能,而这个解法剑出奇招,思路很是新鲜。


程序员灯塔
转载请注明原文链接:LeetCode-加油站
喜欢 (0)