134, 加油站

一、题目描述

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

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

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

示例 1
输入: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
输出: 3
解释:
从3号加油站(索引为3处)出发，可获得4升汽油。此时油箱有0 + 4 = 4升汽油
开往4号加油站，此时油箱有4 - 1 + 5 = 8升汽油
开往0号加油站，此时油箱有8 - 2 + 1 = 7升汽油
开往1号加油站，此时油箱有7 - 3 + 2 = 6升汽油
开往2号加油站，此时油箱有6 - 4 + 3 = 5升汽油
开往3号加油站，你需要消耗5升汽油，正好足够你返回到3号加油站。
因此，3可为起始索引。

示例 2
输入: gas = [2, 3, 4], cost = [3, 4, 3]
输出: -1
解释:
你不能从0号或1号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从2号加油站出发，可以获得4升汽油。此时油箱有0 + 4 = 4升汽油
开往0号加油站，此时油箱有4 - 3 + 2 = 3升汽油
开往1号加油站，此时油箱有3 - 3 + 3 = 3升汽油
你无法返回2号加油站，因为返程需要消耗4升汽油，但是你的油箱只有3升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示

• n == gas.length == cost.length
• 1 <= n <= 10⁵
• 0 <= gas[i], cost[i] <= 10⁴

相关主题

• 贪心
• 数组

二、题解

方法 1: 暴力解法

pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
    let (len, mut start, mut curr_gas) = (gas.len(), 0, 0);

    'outer: for i in 0..len {
        start = len;
        for j in i..len {
            if gas[j] >= cost[j] {
                start = j;
                break;
            }
        }

        if start == len {
            break;
        }

        curr_gas = gas[start] - cost[start];
        for i in (start + 1..len).chain(0..start) {
            curr_gas += gas[i];
            if curr_gas < cost[i] {
                continue 'outer;
            }
            curr_gas -= cost[i];
        }

        return start as i32;
    }

    return -1;
}

public int canCompleteCircuit(int[] gas, int[] cost) {
    int len = gas.length, start, curr_gas;

    outer: for (int i = 0; i < len; i++) {
        start = len;
        for (int j = i; j < len; j++) {
            if (gas[j] >= cost[j]) {
                start = j;
                break;
            }
        }

        if (start == len) {
            break;
        }

        curr_gas = gas[start] - cost[start];
        for (int j = 1; j < len; j++) {
            int k = (start + j) % len;
            curr_gas += gas[k];
            if (curr_gas < cost[k]) {
                continue outer;
            }
            curr_gas -= cost[k];
        }

        return start;
    }

    return -1;
}

func canCompleteCircuit(gas []int, cost []int) int {
    size, start, currGas := len(gas), 0, 0

outer:
    for i := 0; i < size; i++ {
        start = size
        for j := i; j < size; j++ {
            if gas[j] >= cost[j] {
                start = j
                break
            }
        }
        
        if start == size {
            break
        }
        
        currGas = gas[start] - cost[start]
        for j := 1; j < size; j++ {
            k := (start + j) % size
            currGas += gas[k]
            if currGas < cost[k] {
                continue outer
            }
            currGas -= cost[k]
        }
        
        return start
    }

    return -1
}

方法 2: 遍历一次

pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
    let (len, mut i) = (gas.len(), 0);

    while i < len {
        let (mut sum_of_gas, mut sum_of_cost, mut cnt) = (0, 0, 0);

        while cnt < len {
            let j = (i + cnt) % len;
            sum_of_gas += gas[j];
            sum_of_cost += cost[j];
            if sum_of_cost > sum_of_gas {
                break;
            }
            cnt += 1;
        }

        if cnt == len {
            return i as i32;
        } else {
            i += cnt + 1;
        }
    }

    return -1;
}

public int canCompleteCircuit(int[] gas, int[] cost) {
    int len = gas.length, i = 0;

    while (i < len) {
        int sumOfGas = 0, sumOfCost = 0, cnt = 0;

        while (cnt < len) {
            int j = (i + cnt) % len;
            sumOfGas += gas[j];
            sumOfCost += cost[j];
            if (sumOfCost > sumOfGas) {
                break;
            }
            cnt++;
        }

        if (cnt == len) {
            return i;
        } else {
            i += cnt + 1;
        }
    }

    return -1;
}

func canCompleteCircuit(gas []int, cost []int) int {
    size, i := len(gas), 0

    for i < size {
        sumOfGas, sumOfCost, cnt := 0, 0, 0

        for cnt < size {
            j := (i + cnt) % size
            sumOfGas += gas[j]
            sumOfCost += cost[j]
            if sumOfCost > sumOfGas {
                break
            }
            cnt++
        }

        if cnt == size {
            return i
        } else {
            i += cnt + 1
        }
    }

    return -1
}