algorithm - 力扣加油站

Question

我遇到了一个 gas station problem来自 leetcode。它可以在 O(n) 中解决，因为如果从站点 i 开始，当到达站点 j 时，没有足够的气体继续到 j+1 站点，那么从 i 到站点都没有j 可以用作起点。在 another post提供了类似的方法。

我认为，假设油箱有无限的存储空间，这一事实是成立的。如果储 jar 有最大存储量怎么办(即，如果 sum + gas[i] > MAXN，则 sum = MAXN，否则 sum += gas[i] 在每个站)？在这种情况下，从 i 到 j 的站都不能用作起点不一定是真的。那么问题还有O(n)的解法吗？

Answer 1

In such a case it is not necessarily true that none of the stations from i to j can be used as a starting point.

那不是真的。做更多的限制不会导致更多可能的起点，它会导致更少。最佳候选起点仍然是原始算法返回的起点。如果在任何一个站你的油已经满了，而你在完成一个完整的圆圈之前就用完了，那么就没有解决方案。

假设您加油的最后一站是第 i 站，而在第 i+k 站没油了。这意味着，在 i 和 i+k 站之间，您到达时总是至少有 0 油。因此，如果您从那里开始时的汽油为 0，那么您无论如何都会在第 i+k 站用完它。如果您从第 i+k 个站或之后的任何一个站开始，从第 i 个站到第 i+k 个站，您仍然会用完汽油。

所以要解决这个问题，首先要用原来的算法找到最好的候选站点，然后从结果站点出发进行第二轮，看看能不能回到起点。如果不能，则没有解决方案。

原始问题的最佳解决方案可确保在每个站点都拥有尽可能多的汽油。因此，如果该起点导致一个成功的圆圈，那么原始算法返回的所有其他起点也将起作用。

编辑:

要找到其他解决方案，请在 canCompleteCircuit 之后执行(未测试):

int findOtherSolutions(vector<int> &gas, vector<int> &cost, int bestStation, int totalGasLeft) {
  int sum = totalGasLeft;
  int min = totalGasLeft;
  vector<int> solutions;
  solutions.push_back(bestStation);
  for(int i = bestStation-1; i != bestStation ; --i){
    sum -= gas[i]-cost[i];
    if(sum <= min){
      min = sum;
      solutions.push_back(i); 
    }
    if(i==0){
       i = gas.size();
    }
  }
  return solutions;
}

请注意，您必须修改 canCompleteCircuit 才能获得总的剩余气体:

int canCompleteCircuit(vector<int> &gas, vector<int> &cost, int &total) {
  int sum = 0;
  int j = -1;
  for(int i = 0; i < gas.size() ; ++i){
    sum += gas[i]-cost[i];
    total += gas[i]-cost[i];
    if(sum < 0){
      j=i; sum = 0; 
    }
  }
  return total>=0? j+1 : -1;
}