LeetCode经典例题｜134. 加油站｜运用坐标系数学思维一步解决

男娘i 2024-03-26 15:36 87阅读 0赞

## 134. 加油站 ##

![在这里插入图片描述][ba9bc2af71ab44699cd652eff7eba49b.png]  
这道题刚看很容易就想到了暴力或者回溯+剪枝。  
这是一个有增有减的过程，就好像坐标系上的一个个点，连在一起形成一条上下起伏的折线。

### 1. 做坐标轴 ###

比如 gas = \[1,2,3,4,5\], cost = \[3,4,5,1,2\]  
从0号汽车站开始出发，一直到回到起点，存油量折现。  
![图1][1]  
当它从0号加油站行驶到3号加油站的时候，存油量还剩-6，这个时候是存油量最低的时候。  
我们可以再试着从1号加油站、2号加油站出发试试  
![在这里插入图片描述][d6669e8992fd4a84b027e1d48f9f1e06.png]  
**从1号加油站出发，也就意味着此时邮箱为空，也就是X坐标轴其实移动1号加油站，然后把之前的0-1号线段，拼凑到最后面。**  
所以折线自身其实并没有改变，起伏的趋势依然一样，最低点无论坐标轴以什么为0点，都还是最低点。  
![在这里插入图片描述][bda01b2f1d9a4f76a576680d675ff167.png]  
这一段必须理解，不然理解不了什么情况下说明存在解。

同时，从2号加油站出发，也是同理  
![11111][]

注意一下坐标含义

> (3,-2): 从2号加油站出发，到达3号加油站的时候，我的油量只剩下-2了。

### 2. 从何时开始最优 ###

很明显，从油箱油量最低的那一站A开始，去出发，肯定是最优解。  
因为从A往后，油箱里的油量肯定都是要高于那一站的。  
换句话说，无论从哪一个加油站开始，到达A时，邮箱油量肯定是最低。  
只有从这一站出发，才能保证后续的补给足够。  
从坐标轴来看，以最低点为原点，各站点存油量为正数才有可能最多。

### 3. 什么时候保证是有解的 ###

如果只考虑某个点存油量是不是负数，明显有问题，因为它后续的加油站可以再存。  
但是如果我们是以最低点A为原点，最终肯定还是到达A站点时，它的存油量是最少的。  
上面已经分析过，曲线的起伏趋势是不会变的，最低点永远都是最低点。  
那我们只要保证：  
以最低点A为起点，最终再到达A站点时，它的存油量>=0，说明肯定够。  
由于解唯一，而A是最优解，说明A就是唯一解。

### 4. 代码 ###

class Solution {
        
        public int canCompleteCircuit(int[] gas, int[] cost) {
        
            // 做存油坐标系，找到存油量最少的点minIndex，以它为起点。
            int space=0;
            int minSpace=Integer.MAX_VALUE;
            int minIndex=0;
            for(int i=0;i<gas.length;i++){
        
                // 存油量
                space += gas[i]-cost[i];
                if(minSpace > space){
        
                    minSpace = space;
                    minIndex = i;
                }
            }
            // 如果最后存油量<0,说明肯定是不够的
            return space>=0 ? (minIndex+1)%gas.length : -1;
        }
    }

为什么最后是返回minIndex+1呢

比如遍历从0开始，gas\[i\]-cost\[i\]=-2,那就满足，于是minIndex=0，它已经减去了当前站到下一站的耗油量，实际意义是，从0站出发后，到达一站时存油量最少，为-2。  
假设求出2站为最低点，就是从0站一直从2站出发后，到达3站时，存油量最少。  
那我们当然是要从3站出发。

总结：思路很值得借鉴，以坐标轴的形式来思考此类问题。但是坐标点含义，以及代码中定义的细节等需要注意。

![在这里插入图片描述][efd8b6eb569144bd830406b3c0b1f156.png]

[ba9bc2af71ab44699cd652eff7eba49b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/456d7c5ed4844e34b385efa31eb2c03a.png
[1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/9aaeb2275f074501acf18db294e41452.png
[d6669e8992fd4a84b027e1d48f9f1e06.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/74f3ea83f2584e90b70166a7ef94cc9b.png
[bda01b2f1d9a4f76a576680d675ff167.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8d15f59d64cd4191853274fe6ec92b3a.png
[11111]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/9bc0edd33ce7459c91fc88ae7e9c0cac.png
[efd8b6eb569144bd830406b3c0b1f156.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6c0a4790ab38408cab4fd39713e90db3.png