LeetCode 134. 加油站

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
相似题目

题目描述

✅ 134. 加油站

思路分析

解法一：贪心（推荐）

核心思路：

若所有加油站的油量总和 >= 消耗总和，则必然存在一个起点能跑完全程。

从起点 0 开始累加油量差值（gas[i] - cost[i]），一旦累计值变为负数，说明当前起点到 i 之间的任意一站都不可能作为起点，重置起点为 i + 1，并清零累计值。

一次遍历即可同时完成”是否有解”和”找起点”两件事。

复杂度分析：

时间复杂度：O(n)，其中 n 为加油站数量，只需一次线性遍历。

空间复杂度：O(1)，只使用常数级别的额外变量。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // totalSum 记录全程总油量差，用于判断是否有解
        int totalSum = 0;
        // curSum 记录从当前起点出发的累计油量差
        int curSum = 0;
        // start 记录当前候选起点
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            totalSum += diff;
            curSum += diff;

            // 累计油量为负，说明从 start 到 i 均不可作为起点
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }

        // 总油量不足，无解返回 -1
        if (totalSum < 0) {
            return -1;
        }
        return start;
    }
}

func canCompleteCircuit(gas []int, cost []int) int {
    // totalSum 记录全程总油量差，用于判断是否有解
    totalSum := 0
    // curSum 记录从当前候选起点出发的累计油量差
    curSum := 0
    // start 记录当前候选起点
    start := 0

    for i := 0; i < len(gas); i++ {
        diff := gas[i] - cost[i]
        totalSum += diff
        curSum += diff

        // 累计油量为负，说明从 start 到 i 均不可作为起点
        if curSum < 0 {
            start = i + 1
            curSum = 0
        }
    }

    // 总油量不足，无解返回 -1
    if totalSum < 0 {
        return -1
    }
    return start
}

相似题目

题目	难度	考察点
45. 跳跃游戏 II	中等	贪心
55. 跳跃游戏	中等	贪心
406. 根据身高重建队列	中等	贪心
135. 分发糖果	困难	贪心
860. 柠檬水找零	简单	贪心
1005. K 次取反后最大化的数组和	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/82572488