134. 加油站 Krains 2020-08-20 14:03:21 前缀和贪心

Krains

发布于 2020-08-22 17:50:36

2290

发布于 2020-08-22 17:50:36

文章被收录于专栏：KrainsKrains

解题思路

首先明确一点，如果加油站提供的油总和大于等于花费的油总和，那么必定可以绕环路行驶一周
我们尝试从编号0出发，不管油够不够，一直走到尾，期间记录gas[i]与cost[i]差值的总和sum，同时计算行驶过程中油箱中油量的最小值min（可以为负）。
如果总和sum<0，那么无论如何都不能够环绕一周，如果大于等于0，那么一定可以环绕一周
如果此时min>=0，那么行驶过程中油箱始终不为空，此时可以从0出发环绕一周
如果min<0，那么考虑更换起点，从右往左枚举起点，此时行驶方向还是从左往右，将min补充到大于0的点就是能够环绕一周的起始点，因为此时从新的起点出发，那么min>=0，这表示行驶过程中油箱始终不为空。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        int min = 0;
        for(int i = 0; i < gas.length; i++){
            // 统计加油量和耗油量
            sum += gas[i] - cost[i];
            min = Math.min(min, sum);
        }
        // 如果小于0，则不能环绕一周
        if(sum < 0)
            return -1;
        // 此时从起点出发能够环绕一周
        if(min >= 0)
            return 0;
        for(int i = gas.length-1; i >= 0; i--){
            int diff = gas[i] - cost[i];
            min += diff;
            // 如果该点能够将min补充到大于等于0，则该点为起点
            if(min >= 0)
                return i;
        }
        return -1;
    }
}

# 前缀和求最大子数组和

与该题十分类似53. 最大子序和

当然也需要借助贪心的思想，如果总加油量和耗油量大于等于0那么总可以环绕一周，我们用diff[i]=gas[i]-cost[i]得到一个数组，我们找到是该数组的最大子数组和的开始元素索引k，从k出发总能环绕一周。

因为数组是一个环路，我们可以将数组diff复制一份到该数组的末尾，然后用前缀和求出最大子数组和。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 前缀和
        int sum = 0;
        // 记录遍历过程中的最小前缀和，初始化为0表示前缀和的首元素是0
        int min = 0;
        int j = 0;
        int k = 0;
        int maxSum = 0;
        int n = gas.length;
        int[] diff = new int[2 * n];
        for(int i = 0; i < n; i++){
            diff[i] = gas[i] - cost[i];
            diff[i+n] = diff[i];
        }
        for(int i = 0; i < diff.length; i++){
            sum += diff[i];
            // 求最大子数组，更新下标k
            if(sum-min > maxSum){
                maxSum = sum-min;
                k = j;
            }
            // min是当前最小的前缀和，j记录最小前缀和的开始元素下标
            if(min > sum){
                j = i+1;
                min = sum;
            }
        }
        if(sum < 0)
            return -1;
        return k % n;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/08/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法