题解 | #大胃王牛牛#

知识点

贪心

解题思路

使用totalGas变量来计算总的油料量，使用currGas变量来记录当前剩余的油料量。

如果当前剩余油料量小于0，说明无法到达下一个牛棚，需要重新选择起点并重置剩余油料量。否则，我们将剩余油料量增加当前牛棚的草料减去消耗的油料。

最后，判断总的油料量是否小于0，如果是，则返回-1表示无法走完一圈；否则返回起点位置加1，即为最终结果。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grass int整型一维数组
     * @param cost int整型一维数组
     * @return int整型
     */
    public int can_complete_circuit (int[] grass, int[] cost) {
        // write code here
        int n = grass.length;

        int totalGas = 0; // 总的油料量
        int currGas = 0; // 当前剩余油料量
        int start = 0; // 记录起点位置

        for (int i = 0; i < n; i++) {
            totalGas += (grass[i] - cost[i]);

            // 当前剩余油料量小于0，无法到达下一个牛棚
            if (currGas < 0) {
                // 重新开始
                start = i;
                currGas = grass[i] - cost[i];
            } else {
                currGas += (grass[i] - cost[i]);
            }
        }

        // 如果总的油料量小于0，说明无法走完一圈
        if (totalGas < 0) {
            return -1;
        }

        return start + 1;
    }
}