---
# System prepended metadata

title: 134. Gas Station
tags: [LeetCode]

---

###### tags: `LeetCode`
# 134. Gas Station

## 題目

一個環狀路線有n個加油站，給每站可以加的油和到下一站需要的油，求是否能從其中一站繞一圈回原點，並回傳該站位置(有唯一解)。

## 概念
- 用greedy演算法。
- 若總共需要的油量 > 總共可以加的油量，則無法繞一圈，回傳-1。
- cur_gas = cur_gas + gas[i] - cost[i];
    若cur_gas小於0，則代表此起始點不是個好的點，要從下一個點開始。

## 程式碼

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