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; // 情况1if (min >= 0) return 0; // 情况2// 情况3for (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一旦小于0start = i + 1; // 起始位置更新为i+1curSum = 0; // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
};时间复杂度O(N)
转载于代码随想录，大佬的算法