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
        {
            if(gas[i] < cost[i]) 
            {
                continue;
            }
            else{
                index = i; 
                int j = index;
                int count = 0;
                cout<<"index="<
                while(true)
                {
                    j = j%n;
                    cout<<"j="<
                    if(left < 0) 
                    {
                        left = 0;
                        break;
                    }
                    if(count == n)
                    {
                        flag = true;
                        return index;
                    }
                    left = left + gas[j] - cost[j];
                    cout<<"left="<
                    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) 

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