文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题加油站出处134. 加油站难度6 级题目描述要求在一条环路上有n \texttt{n}n个加油站其中第i \texttt{i}i个加油站有汽油gas[i] \texttt{gas[i]}gas[i]升。有一辆油箱容量无限的的汽车从第i \texttt{i}i个加油站开往第i 1 \texttt{i} \texttt{1}i1个加油站需要消耗汽油cost[i] \texttt{cost[i]}cost[i]升。从其中的一个加油站出发初始时油箱为空。给定两个整数数组gas \texttt{gas}gas和cost \texttt{cost}cost如果可以绕环路行驶一周则返回出发时加油站的编号否则返回-1 \texttt{-1}-1。如果存在解则保证解是唯一的。示例示例 1输入gas [1,2,3,4,5], cost [3,4,5,1,2] \texttt{gas [1,2,3,4,5], cost [3,4,5,1,2]}gas [1,2,3,4,5], cost [3,4,5,1,2]输出3 \texttt{3}3解释从3 \texttt{3}3号加油站下标3 \texttt{3}3出发可获得4 \texttt{4}4升汽油。此时油箱有0 4 4 \texttt{0} \texttt{4} \texttt{4}044升汽油。开往4 \texttt{4}4号加油站此时油箱有4 − 1 5 8 \texttt{4} - \texttt{1} \texttt{5} \texttt{8}4−158升汽油。开往0 \texttt{0}0号加油站此时油箱有8 − 2 1 7 \texttt{8} - \texttt{2} \texttt{1} \texttt{7}8−217升汽油。开往1 \texttt{1}1号加油站此时油箱有7 − 3 2 6 \texttt{7} - \texttt{3} \texttt{2} \texttt{6}7−326升汽油。开往2 \texttt{2}2号加油站此时油箱有6 − 4 3 5 \texttt{6} - \texttt{4} \texttt{3} \texttt{5}6−435升汽油。开往3 \texttt{3}3号加油站消耗5 \texttt{5}5升汽油正好足够返回到3 \texttt{3}3号加油站。因此返回3 \texttt{3}3作为起始下标。示例 2输入gas [2,3,4], cost [3,4,3] \texttt{gas [2,3,4], cost [3,4,3]}gas [2,3,4], cost [3,4,3]输出-1 \texttt{-1}-1解释不能从0 \texttt{0}0号或1 \texttt{1}1号加油站出发因为没有足够的汽油可以行驶到下一个加油站。从2 \texttt{2}2号加油站出发可获得4 \texttt{4}4升汽油。此时油箱有0 4 4 \texttt{0} \texttt{4} \texttt{4}044升汽油。开往0 \texttt{0}0号加油站此时油箱有4 − 3 2 3 \texttt{4} - \texttt{3} \texttt{2} \texttt{3}4−323升汽油。开往1 \texttt{1}1号加油站此时油箱有3 − 3 3 3 \texttt{3} - \texttt{3} \texttt{3} \texttt{3}3−333升汽油。无法返回2 \texttt{2}2号加油站因为返程需要消耗4 \texttt{4}4升汽油但是油箱只有3 \texttt{3}3升汽油。因此无论从哪个加油站出发都不可能绕环路行驶一周。数据范围n gas.length cost.length \texttt{n} \texttt{gas.length} \texttt{cost.length}ngas.lengthcost.length1 ≤ n ≤ 10 5 \texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{5}1≤n≤1050 ≤ gas[i], cost[i] ≤ 10 4 \texttt{0} \le \texttt{gas[i], cost[i]} \le \texttt{10}^\texttt{4}0≤gas[i], cost[i]≤104解法思路和算法环路上有n nn个加油站需要找到可以绕环路行驶一周的出发加油站的编号。朴素的做法是分别尝试从每个加油站出发判断是否可以绕环路行驶一周该做法需要尝试n nn个起点每个起点需要O ( n ) O(n)O(n)的时间遍历和判断时间复杂度是O ( n 2 ) O(n^2)O(n2)该时间复杂度过高需要优化。为了降低时间复杂度需要跳过不可能作为起点的加油站。当汽车位于第i ii个加油站时获得gas [ i ] \textit{gas}[i]gas[i]升汽油行驶到下一个加油站需要消耗cost [ i ] \textit{cost}[i]cost[i]升汽油因此汽车从第i ii个加油站行驶到下一个加油站的汽油变化量是gas [ i ] − cost [ i ] \textit{gas}[i] - \textit{cost}[i]gas[i]−cost[i]升。初始时油箱中的汽油是零如果行驶到一个加油站的剩余汽油是负数则无法行驶到该加油站。汽车绕环路行驶一周的汽油变化量是sum ∑ i 0 n − 1 ( gas [ i ] − cost [ i ] ) \textit{sum} \sum_{i 0}^{n - 1} (\textit{gas}[i] - \textit{cost}[i])sum∑i0n−1​(gas[i]−cost[i])。如果sum 0 \textit{sum} 0sum0则无论从哪个加油站出发绕环路行驶一周之后的剩余汽油都是负数因此不可能绕环路行驶一周返回− 1 -1−1。如果sum ≥ 0 \textit{sum} \ge 0sum≥0则一定存在一个加油站作为起点可以绕环路行驶一周。如果汽车从第i ii个加油站出发可以行驶到第j jj个加油站且不能行驶到第j 1 j 1j1个加油站其中i ≠ j i \ne jij且从第i ii个加油站行驶到第j jj个加油站经过的加油站数量小于n nn则从第i ii个加油站到第j jj个加油站都不可能作为起点将第j 1 j 1j1个加油站作为可能的起点继续尝试。理由如下。汽车位于第i ii个加油站时的汽油是零位于从第i 1 i 1i1个加油站到第j jj个加油站的任意一个加油站时汽油都是非负数位于第j 1 j 1j1个加油站时汽油是负数。用f ( x , y ) f(x, y)f(x,y)表示汽车从第x xx个加油站行驶到第y yy个加油站的汽油变化量则f ( i , j ) ≥ 0 f(i, j) \ge 0f(i,j)≥0且f ( i , j 1 ) 0 f(i, j 1) 0f(i,j1)0。在从第i ii个加油站到第j jj个加油站的途中任选一个加油站记为第k kk个加油站则f ( i , j ) f ( i , k ) f ( k , j ) f(i, j) f(i, k) f(k, j)f(i,j)f(i,k)f(k,j)f ( i , k ) ≥ 0 f(i, k) \ge 0f(i,k)≥0因此f ( k , j ) ≤ f ( i , j ) f(k, j) \le f(i, j)f(k,j)≤f(i,j)f ( k , j 1 ) f ( k , j ) f ( j , j 1 ) ≤ f ( i , j ) f ( j , j 1 ) f ( i , j 1 ) 0 f(k, j 1) f(k, j) f(j, j 1) \le f(i, j) f(j, j 1) f(i, j 1) 0f(k,j1)f(k,j)f(j,j1)≤f(i,j)f(j,j1)f(i,j1)0即如果从第k kk个加油站出发则一定不可能行驶到第j 1 j 1j1个加油站因此第k kk个加油站不能作为起点可能作为起点的加油站一定在第j jj个加油站之后。遍历过程中维护当前作为起点的加油站下标start \textit{start}start初始时start 0 \textit{start} 0start0。当start i \textit{start} istarti时如果汽车从第i ii个加油站出发可以行驶到第j jj个加油站且不能行驶到第j 1 j 1j1个加油站则将start \textit{start}start的值更新为j 1 j 1j1继续遍历。遍历结束之后如果sum ≥ 0 \textit{sum} \ge 0sum≥0则从下标start \textit{start}start开始一定可以绕环路行驶一周。理由如下。如果start 0 \textit{start} 0start0则遍历过程中任意时刻的汽油都是非负数因此可以绕环路行驶一周。如果start 0 \textit{start} 0start0则从下标start \textit{start}start到下标n − 1 n - 1n−1的过程中任意时刻的汽油都是非负数。假设存在下标j jj满足j start j \textit{start}jstart且行驶到下标j jj处的汽油是负数则将行程分成三段第一段从下标start \textit{start}start到下标n − 1 n - 1n−1第二段从下标n − 1 n - 1n−1到下标j jj第三段从下标j jj到下标start \textit{start}start此时第三段的汽油变化一定是正数一定可以在第三段找到一个加油站作为起点在遍历到start \textit{start}start之前就会遍历到正确的起点。因此不存在下标j jj使得行驶到下标j jj处的汽油是负数。根据上述分析可以使用贪心的思想寻找作为起点的加油站。从下标0 00开始从左到右遍历数组gas \textit{gas}gas和cost \textit{cost}cost遍历过程中维护起点start \textit{start}start、汽油变化量总和sum \textit{sum}sum与当前剩余汽油量remain \textit{remain}remain初始时start \textit{start}start、sum \textit{sum}sum与remain \textit{remain}remain都是0 00。当遍历到下标i ii时执行如下操作。计算difference gas [ i ] − cost [ i ] \textit{difference} \textit{gas}[i] - \textit{cost}[i]differencegas[i]−cost[i]将sum \textit{sum}sum和remain \textit{remain}remain分别加difference \textit{difference}difference。如果remain 0 \textit{remain} 0remain0则将start \textit{start}start更新为i 1 i 1i1将remain \textit{remain}remain更新为0 00。遍历结束之后如果sum ≥ 0 \textit{sum} \ge 0sum≥0则返回start \textit{start}start否则返回− 1 -1−1。代码classSolution{publicintcanCompleteCircuit(int[]gas,int[]cost){intstart0;intsum0,remain0;intngas.length;for(inti0;in;i){intdifferencegas[i]-cost[i];sumdifference;remaindifference;if(remain0){starti1;remain0;}}returnsum0?start:-1;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是数组gas \textit{gas}gas和数组cost \textit{cost}cost的长度。需要遍历两个数组一次。空间复杂度O ( 1 ) O(1)O(1)。