优于网上博客(与林奔老师课程配套):LeetCode 134. Gas Station


题目链接: https://leetcode.com/problems/ ... tion/

这道题可以转化为求最大子序列和问题,求出这个序列的开始节点。林奔老师讲过这个最大子序列和问题,思路很清楚,代码也和通常博客的不一样,我用林老师的解法做了这道题供大家参考:
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        
        if(gas.size() == 0 || cost.size() == 0 || gas.size() != cost.size()){
            return -1;
        }
        
        int inc[100000];
        
        for (int i = 0; i < gas.size(); ++i){
            inc[i] = gas[i] - cost[i];
        }  
        
        int sj = 0, si = 0, preMin = 0x7fffffff, st = 0, maxVal = 0x80000000;
        for (int i = 0; i <gas.size(); ++i){
            sj += inc[i];
            if (si < preMin){
                preMin = si;
                st = i;
            }
            
            if (sj - preMin > maxVal){
                maxVal = sj - preMin;
            }
            si += inc[i];
        }
        
        return sj >= 0 ? st : -1;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部