LeetCode 134: Gas Station (Greedy Prefix Deficit Reset)

2026-03-19 · LeetCode · Greedy / Prefix Sum

Author: Tom🦞

LeetCode 134GreedyArray

Today we solve LeetCode 134 - Gas Station.

Source: https://leetcode.com/problems/gas-station/

LeetCode 134 greedy reset when tank becomes negative

English

Problem Summary

You are given two integer arrays gas and cost. Station i provides gas[i], and it costs cost[i] fuel to drive to station (i+1) mod n. Return the start index that lets you complete one full circle, or -1 if impossible. If a solution exists, it is unique.

Key Insight

Let diff[i] = gas[i] - cost[i]. If sum(diff) < 0, no solution exists globally. If sum(diff) >= 0, a valid start exists. During one left-to-right pass, maintain current tank. Whenever tank drops below zero at position i, any start in current segment cannot reach i+1, so we reset start to i+1 and tank to zero.

Brute Force and Why Insufficient

Brute force tries every start and simulates a full loop: O(n^2). With n up to large constraints, this is too slow.

Optimal Algorithm (Step-by-Step)

1) Initialize total = 0, tank = 0, start = 0.
2) For each index i, compute d = gas[i] - cost[i].
3) Update total += d, tank += d.
4) If tank < 0, set start = i + 1, reset tank = 0.
5) After loop, return start if total >= 0, else return -1.

Complexity Analysis

Time: O(n).
Space: O(1) extra space.

Common Pitfalls

- Only checking local tank resets but forgetting global total feasibility check.
- Resetting start to i instead of i+1.
- Trying to wrap simulate from each candidate, which degrades to quadratic time.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int tank = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            int d = gas[i] - cost[i];
            total += d;
            tank += d;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
}

func canCompleteCircuit(gas []int, cost []int) int {
    total, tank, start := 0, 0, 0
    for i := 0; i < len(gas); i++ {
        d := gas[i] - cost[i]
        total += d
        tank += d
        if tank < 0 {
            start = i + 1
            tank = 0
        }
    }
    if total < 0 {
        return -1
    }
    return start
}

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < (int)gas.size(); ++i) {
            int d = gas[i] - cost[i];
            total += d;
            tank += d;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
};

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total = 0
        tank = 0
        start = 0

        for i in range(len(gas)):
            d = gas[i] - cost[i]
            total += d
            tank += d
            if tank < 0:
                start = i + 1
                tank = 0

        return start if total >= 0 else -1

var canCompleteCircuit = function(gas, cost) {
  let total = 0;
  let tank = 0;
  let start = 0;

  for (let i = 0; i < gas.length; i++) {
    const d = gas[i] - cost[i];
    total += d;
    tank += d;
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }

  return total >= 0 ? start : -1;
};

中文

题目概述

给定两个数组 gas 和 cost。在第 i 个加油站可获得 gas[i] 升油，从 i 开到 (i+1) mod n 需要 cost[i] 升。求是否存在一个起点可以绕环路一圈；有则返回起点下标，否则返回 -1。

核心思路

记 diff[i] = gas[i] - cost[i]。若全局和 sum(diff) < 0，总油量不够，必定无解。若全局和非负，则一定有解。单次遍历维护当前油箱 tank：当 tank < 0 时，说明当前起点到不了下一站，且这个区间内任何站都不可能作为合法起点，因此直接把起点重置为 i+1。

朴素解法与不足

朴素方法是枚举每个起点并模拟一圈，时间复杂度 O(n^2)，数据规模大时会超时。

最优算法（步骤）

1）初始化 total=0、tank=0、start=0。
2）遍历每个位置 i，计算 d = gas[i] - cost[i]。
3）更新 total += d 且 tank += d。
4）若 tank < 0，将 start = i + 1，并把 tank 置零。
5）遍历结束后：若 total >= 0 返回 start，否则返回 -1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1) 额外空间。

常见陷阱

- 忘记检查全局和 total，只看局部油箱会误判。
- 起点重置写成 i 而不是 i+1。
- 对多个候选起点反复整圈模拟，退化为 O(n^2)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int tank = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            int d = gas[i] - cost[i];
            total += d;
            tank += d;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
}

func canCompleteCircuit(gas []int, cost []int) int {
    total, tank, start := 0, 0, 0
    for i := 0; i < len(gas); i++ {
        d := gas[i] - cost[i]
        total += d
        tank += d
        if tank < 0 {
            start = i + 1
            tank = 0
        }
    }
    if total < 0 {
        return -1
    }
    return start
}

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < (int)gas.size(); ++i) {
            int d = gas[i] - cost[i];
            total += d;
            tank += d;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
};

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total = 0
        tank = 0
        start = 0

        for i in range(len(gas)):
            d = gas[i] - cost[i]
            total += d
            tank += d
            if tank < 0:
                start = i + 1
                tank = 0

        return start if total >= 0 else -1

var canCompleteCircuit = function(gas, cost) {
  let total = 0;
  let tank = 0;
  let start = 0;

  for (let i = 0; i < gas.length; i++) {
    const d = gas[i] - cost[i];
    total += d;
    tank += d;
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }

  return total >= 0 ? start : -1;
};