> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/134.-gas-station.md).

# 134. Gas Station

## 1.問題 

* 在這個加油站可以補充gas\[i], 但到下個加油站時將會消耗cost\[i], 請問從哪個點出發可以順利順時針旅行一圈回到原本的加油站?

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNXckvOPwfqYEo2Ylft%2F-LNXdYDnp-06k76lPSWK%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-29%20%E4%B8%8A%E5%8D%888.06.28.png?alt=media\&token=206eda69-e933-4098-845f-1bc448631d50)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
* function header, parameter
* test input
* 觀察
  * 選擇出發的加油站
  * 環遊一圈
* 說明想法
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        if (gas.empty() || 
            cost.empty() ||
            gas.size() != cost.size()){
            return -1;
        }
        int size = gas.size();
        for (int i = 0 ; i < size; i++) {
            if (gas[i] - cost[i] >= 0) {
                int start = i;
                int val = 0, cnt = 0;
                while (val >= 0) {
                    if (cnt == size) {
                        return i;
                    }
                    val += gas[start];
                    val -= cost[start];
                    start = (start + 1) % size;
                    cnt++;
                }
            }
        }
        
        return - 1;
    }
};
```