加油站

解题思路：挨个检查是否满足gas[i] - cost[i] >= 0 如果满足，则说明该加油站有充足的油驶往下一个加油站，则开始模拟加油过程。时间复杂度o(n^2).

import java.util.*;
public class Solution {
    public int gasStation (int[] gas, int[] cost) {
        int res = 0;
        for(int i = 0; i < gas.length; ++i) {
            if(gas[i] < cost[i]) continue;
            res = gas[i];
            for(int j = 0; j < gas.length; ++j) {
                res -= cost[(j + i) % gas.length];
                if(res < 0) break;
                res += gas[(j + i + 1) % gas.length];
            }
            if(res >= 0) return i;
        }
        return -1;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param gas int整型一维数组
     * @param cost int整型一维数组
     * @return int整型
     */
    public int gasStation(int[] gas, int[] cost) {
        int n = gas.length;
        
        // 用一个数组来存储每个加油站的油量差：gas[i] - cost[i]
        int[] left = new int[n * 2];
        for (int i = 0; i < n; i++) {
            left[i] = gas[i] - cost[i];         // 前半部分：从前往后计算油量差
            left[n + i] = left[i];              // 后半部分：复制前半部分，模拟环形路线
        }

        // 计算从每个加油站出发的情况
        int index = 0;  // 从第一个加油站开始
        while (index < n) {
            if (left[index] < 0) {
                index++;  // 如果当前位置油量不足，跳过这个点
                continue;
            }

            boolean flag = true;  // 假设从index出发能绕一圈
            int tmp = 0;          // 当前油量

            // 从index开始，向后检查是否能够顺利绕一圈
            for (int i = index; i < left.length && flag; i++) {
                tmp += left[i];   // 累加油量差
                if (tmp < 0) {    // 如果油量为负，表示无法继续
                    flag = false;
                }
            }
 
            // 如果前面没有失败，再从环的前半部分继续检查
            for (int i = 0; i < index && flag; i++) {
                tmp += left[i];   // 累加油量差
                if (tmp < 0) {    // 如果油量为负，表示无法继续
                    flag = false;
                }
            }

            // 如果能够绕一圈，返回当前的出发点index
            if (flag) {
                return index;
            }

            // 如果无法绕一圈，继续尝试下一个出发点
            index++;
        }

        // 如果所有起点都无法绕一圈，返回-1
        return -1;
    }
}

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int gasStation(vector<int>& gas, vector<int>& cost) {
        int curSum=0;
        int min=INT_MAX;
        for(int i=0;i<gas.size();i++)
        {
            int rest=gas[i]-cost[i];
            curSum+=rest;
            if(curSum<min)
                min=curSum;
        }
        if(curSum<0)
            return -1;
        if(min>=0)
            return 0;
        for(int i=gas.size()-1;i>=0;i--)
        {
            int rest=gas[i]-cost[i];
            min+=rest;
            if(min>=0)
                return i;
        }
        return -1;
    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        int spare=0;
        int minspare=Integer.MAX_VALUE;
        int index=0;
        for(int i=0;i<gas.length;i++){
            spare+=gas[i]-cost[i];
            if(spare<minspare){
                minspare=spare;
                index=i;
            }
        }
        return spare>=0?index+1:-1;
        // write code here
    }
}