LeetCode加油站(贪心算法/暴力，分析其时间和空间复杂度)_算法

题目描述

一.原本暴力算法

最初的想法是：先比较gas数组和cost数组的大小，找到可以作为起始点的站点(因为如果你起始点的油还不能到达下一个站点，就不能作为起始点)。当找到过后，再去依次顺序跑一圈，如果剩余的油为负数，再去寻找下一个满足条件的起始站点。

class solution {
public:
    int cancompletecircuit(vector<int>& gas, vector<int>& cost) {
        int index = -1; //定义初始起点
        int left = 0; //定义剩余油量
        bool flag = false;
        int n = gas.size();
        //寻找起始位置
        for(int i = 0;i<n;i++)
        {
            if(gas[i] < cost[i]) 
            {
                continue;
            }
            else{
                index = i; 
                int j = index;
                int count = 0;
                cout<<"index="<<index<<endl;
                while(true)
                {
                    j = j%n;
                    cout<<"j="<<j<<endl;
                    if(left < 0) 
                    {
                        left = 0;
                        break;
                    }
                    if(count == n)
                    {
                        flag = true;
                        return index;
                    }
                    left = left + gas[j] - cost[j];
                    cout<<"left="<<left<<endl;
                    count++;
                    j++;
                }   

            }
        }

        //判断
        if(flag)
        {
            return index;
        }else{
            return -1;
        }
    }
};

但是代码最后超时了！！

时间复杂度是o(n^2) 因为循环遍历寻找起始站点，找到过后再去循环遍历走一圈是o(n^2）的时间复杂度！

巧妙思路算法二能通过的

转子大佬的代码。

情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

class solution {
public:
    int cancompletecircuit(vector<int>& gas, vector<int>& cost) {
        int cursum = 0;
        int min = int_max; // 从起点出发，油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            cursum += rest;
            if (cursum < min) {
                min = cursum;
            }
        }
        if (cursum < 0) return -1;  // 情况1
        if (min >= 0) return 0;     // 情况2
                                    // 情况3
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

在这里时间复杂度o(n)

空间复杂度o(1)没有开辟新的空间

二.贪心算法

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为cursum，一旦cursum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算cursum。

class solution {
public:
    int cancompletecircuit(vector<int>& gas, vector<int>& cost) {
        int cursum = 0;
        int totalsum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            cursum += gas[i] - cost[i];
            totalsum += gas[i] - cost[i];
            if (cursum < 0) {   // 当前累加rest[i]和 cursum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                cursum = 0;     // cursum从0开始
            }
        }
        if (totalsum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

时间复杂度o(n)

转载于代码随想录，大佬的算法