本文共 558 字，大约阅读时间需要 1 分钟。

N个加油站逆时针组成一个环，每个加油站最多加oil[i]的油量，该加油站距下个加油站距离dis[i]，1个油可以走1个距离，初始车里没有油，则从哪些加油站出发可以逆时针一圈后回到出发点。

类似dp的思维题，时间O(N)

该方法实现O(N)的核心思想在于，先找到一个良好出发点，再顺时针找可以到达该良好出发点的出发点，即新良好出发点，依次顺时针找，若顺时针一圈后仍然没有良好出发点，则所有点都不会是。

过程如下：

首先 ，数组实现环结构，每个元素代表加油站，Arr[i] 取值为 oil[i] - dis[i] ，其中，oil[i] 为当前加油站提供的油，dis[i] 为从加油站 i 到 加油站 i+1 的距离，其中 i+1 可以返回到数组0位置。Arr[i] 新值可以称为净值。

由于车走的方向是逆时针，所以思维处理该题，逆时针扩充联通块，顺时针考查起始位置。

首先，所有净值小于0的加油站一定不满足要求。

所以，先从考查任意净值大于等于0的起始点，然后逆时针扩充联通块。

若能逆时针扩充一圈后回来，则该点是良好出发点，否则不是，同时标记联通块计算的结尾点。

然后从考查点顺时针考查下个不为0的点，是否可以扩充到刚才的考查点，不可以则一定不是良好出发点，若可以，再考查是否可以从刚才结尾点继续扩充一圈，依次类推。。

转载地址：http://rbwji.baihongyu.com/