如何找到满足加油站（Leetcode）问题的所有点？

Question

我想解决与https://leetcode.com/problems/gas-station/description/问题类似的问题：

给定环形路线上的 n 个加油站，第 i 个加油站有 g[i] 个加油站。从站点 i 到 (i+1) 的旅行成本为 c[i]。您的汽车从空油箱开始，并具有无限的储气量。找到所有可以从索引 i 开始并返回到索引 i 的起始索引 i

对于这个问题（n<=1e5)

）我想不出比 O(n^2) （一个明显的解决方案）更好的解决方案

Answer 1

你可以用 O(N) 时间复杂度一次性解决它：

• 检查

  gas

  和

  cost

  的每个元素，并且

  tank

  将是

  tank += gas[i] - cost[i]

  。

• 如果

  tank

  降至零以下，那么

  start

  将是下一个加油站，我们将

  tank

  设置回零。

• 如果

  total_gas >= total_cost

  ，有解决方案。

Python

from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total_gas, total_cost, tank, start = 0, 0, 0, 0
        for i, (g, c) in enumerate(zip(gas, cost)):
            total_gas += g
            total_cost += c
            tank += g - c

            if tank < 0:
                start, tank = i + 1, 0

        return start if total_gas >= total_cost else -1


if __name__ == '__main__':
    print(Solution().canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))

打印

3