LeetCode_ 134_ gas station

Topic link

• https://leetcode.cn/problems/gas-station/

Title Description

There is... On a ring road n A gas station , Among them the first i Gas stations have gas gas[i] l .

You have a car with unlimited tank capacity , From i A gas station goes to the i+1 A gas station needs gas cost[i] l . You start from one of the gas stations , The tank is empty at first .

Given two arrays of integers gas and cost , If you can drive around the loop , Then return to the number of the gas station at the time of departure , Otherwise return to -1 . If there is a solution , be Guarantee It is only Of .

Example 1:

 Input : gas = [1,2,3,4,5], cost = [3,4,5,1,2]
 Output : 3
 explain :
 from  3  Gas station ( The index for  3  It's about ) set out , Can be obtained  4  A litre of petrol . Now the tank has  = 0 + 4 = 4  A litre of petrol 
 Go to  4  Gas station , Now the tank has  4 - 1 + 5 = 8  A litre of petrol 
 Go to  0  Gas station , Now the tank has  8 - 2 + 1 = 7  A litre of petrol 
 Go to  1  Gas station , Now the tank has  7 - 3 + 2 = 6  A litre of petrol 
 Go to  2  Gas station , Now the tank has  6 - 4 + 3 = 5  A litre of petrol 
 Go to  3  Gas station , You need to consume  5  A litre of petrol , Just enough for you to return to  3  Gas station .
 therefore ,3  Can be the starting index .

Example 2:

 Input : gas = [2,3,4], cost = [3,4,3]
 Output : -1
 explain :
 You can't  0  Number or  1  Gas station No.1 starts , Because there's not enough gas to get you to the next gas station .
 We from  2  Gas station No.1 starts , You can get  4  A litre of petrol .  Now the tank has  = 0 + 4 = 4  A litre of petrol 
 Go to  0  Gas station , Now the tank has  4 - 3 + 2 = 3  A litre of petrol 
 Go to  1  Gas station , Now the tank has  3 - 3 + 3 = 3  A litre of petrol 
 You can't go back  2  Gas station , Because the return journey costs  4  A litre of petrol , But your tank only has  3  A litre of petrol .
 therefore , No matter what , You can't even drive around the loop .

Tips :

• gas.length == n
• cost.length == n
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

Their thinking

The law of greed

• The remaining quantity of each gas station rest[i] = gas[i] - cost[i]
• i from 0 Start accumulating rest[i], He jizuo curSum, once curSum < 0, explain [0,i] No interval can be used as the starting position , Start from i+1 Count up ,curSum It is also necessary to reset synchronously and accumulate again
• If there is a larger negative number , It's about to be updated i

AC Code

class Solution {
    
    public int canCompleteCircuit(int[] gas, int[] cost) {
    
        int start = 0;
        int curSum = 0;
        int totalSum = 0;
        for (int i = 0; i < gas.length; i++) {
    
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
    
                start = i + 1;
                curSum = 0;
            }
        }
        if (totalSum < 0) {
    
            return -1;
        }
        return start;
    }
}