C++_6ms_Accpeted_With Brief Analysis (This problem also could be converted to "Maximal Sum of Subarray sum")


  • 0

    I think lots of people have finished this question and give some explanations, but some explanation is hard to understand for me, so I tried my own thoughts.

    Maximal sum of Subarray Problem thinking:

    • Suppose you are the driver, you will definitely want to find a start point which could make you store as much as possible gas in an array, and then you could use these gas to pass all of the following stations.
    • Is it familiar to you? Yep, just use remain[i] = gas[i] - cost[i], so you can find the maximal sum of a subarray.

    Another approach:

    • You start at 0, and drive to the some station j, and find that the gas in tank < 0, which means that at station j-1, your tank >= 0, also record the sum of all remain[i]s in this interval.
    • Because we could not reach j from i, so our start point move to the j+1, (because we also could not reach j from i+1.....) and repeat above algorithms.
    • Now suppose that we have find a start point which makes all of the remaining tank > 0, now we are at the end of gas vector, should we switch to the beginning to traverse all of the other factors? Absolutely no, because we have stored our information in the "sum", this records the sum of "remain" from 0 to start - 1, so you can see that all we need to do is just check whether sum + tank >= 0. If it is no less than 0, return start, else return -1.
    class Solution {
    public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int tank = 0, start = 0, sum = 0;
        
        for(int i = 0; i < n; i++){
            tank += gas[i] - cost[i];
            sum += tank;
            if(tank < 0){
               // sum += tank;
                tank = 0;
                start = i + 1;
            }
        }
        return sum < 0 ? -1:start;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.