加油站

871. 最低加油次数

想象成不是只在加油站才能加油，而是只要现在需要油，并且之前有加油站还没有用，那么此时就可以加油。这样一来，如果要使得加油次数最少，那么只要加油就加最多的油，为了保证时间效率，这里用堆来维护前面的未用过的加油站里的油量。需要加油而没有油时(也就是堆为空)，那么就不能够到达，此时返回-1。
这一题就是贪心+优先队列。

class Solution {
  public static int minRefuelStops(int target, int startFuel, int[][] stations) {
    if (target <= startFuel) return 0;
    if (stations.length == 0 && target > startFuel) return -1;
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>((o1, o2) -> (o2 - o1));
    int maxPosition = startFuel;
    int count = 0;
    for (int i = 0; i < stations.length; i++) {
      while (maxPosition < stations[i][0]) {
        if (queue.isEmpty()) return -1;
        maxPosition += queue.poll();
        count++;
      }
      queue.offer(stations[i][1]);
    }
    while (maxPosition < target) {
      if (queue.isEmpty()) return -1;
      maxPosition += queue.poll();
      count++;
    }
    return count;
  }
}

如果加油站没有排过序，需要排序下，可以按照距离升序+油量降序

    Arrays.sort(stations, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        if (o1[0] == o2[0]) return o2[1] - o1[1];
        else return o1[0] - o2[0];
      }
    });

134. 加油站

下面第20行，如果是写成i++，效率会低很多
假设从编号为0站开始，一直到k站都正常，在开往k+1站时车子没油了。这时，应该将起点设置为k+1站。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1; // 超级巧妙的一步
            }
        }
        return -1;
    }
}