134. 加油站

Powered by:NEFU AB-IN

Link

134. 加油站

• 题意

  在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
  你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
  给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

• 思路

  假设i为起点，且i最多不能走到j，结论：[i, j]之前任意起点也 不能走到j
  证明：k是可以走到的，所以left[k] >= 0（即从左边走过来还剩下有油）。 如果把k当作起点即left[k]=0,那么还是走不到j，所以下一次枚举起点，可以直接跳过[i- j],O(n)

• 代码

  class Solution {
  public:
      int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
          int n = gas.size();
          for (int i = 0, j; i < n; ) {  // 枚举起点
              int left = 0;
              for (j = 0; j < n; j ++ ) {
                  int k = (i + j) % n;
                  left += gas[k] - cost[k];
                  if (left < 0) break;
              }
              if (j == n) return i;
              i = i + j + 1;
          }
  
          return -1;
      }
  };
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19