题目描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例：
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3

题目分析

贪心。
当从第 i 个加油站可以移动到 i + 1 时，说明 i + 1 一定不是起点（解唯一），即使后面发现从 i 出发不能环绕一周，也无需从 i + 1 开始出发，直接从 i + x 后出发。
从第一个开始出发，维护总油量 sum，sum < 0 时重置起始点 start。
直到 i = start + length （成功），或 i = 2 * length （失败）。
时间复杂度 O(n)。

Java

public int canCompleteCircuit(int[] gas, int[] cost) {
    int sum = 0;
    int start = Integer.MIN_VALUE;
    for (int i = 0; i < 2 * gas.length; i++) {
        if (i == start + gas.length) {
            return start;
        }
        int index = i % gas.length;
        sum += gas[index] - cost[index];
        if (sum >= 0) {
            if (start == Integer.MIN_VALUE) {
                start = i;
            }
        } else {
            start = Integer.MIN_VALUE;
            sum = 0;
        }
    }
    return -1;
}

Kotlin

fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
    var sum = 0
    val length = gas.size
    var start = Int.MIN_VALUE
    for (i in 0 until 2 * length) {
        if (i == start + length) {
            return start
        }
        val index = i % length
        sum += gas[index] - cost[index]
        if (sum >= 0) {
            if (start == Int.MIN_VALUE) {
                start = i
            }
        } else {
            start = Int.MIN_VALUE
            sum = 0
        }
    }
    return -1
}