Trạm Xăng Vòng TrònGas Station

1function canCompleteCircuit(gas: number[], cost: number[]): number {
2  let total = 0  // tổng chênh lệch cả vòng
3  let tank = 0   // xăng tích luỹ kể từ start hiện tại
4  let start = 0
5  for (let i = 0; i < gas.length; i++) {
6    const diff = gas[i] - cost[i]
7    total += diff
8    tank += diff
9    if (tank < 0) {       // không tới nổi trạm i+1 từ start hiện tại
10      start = i + 1
11      tank = 0
12    }
13  }
14  return total >= 0 ? start : -1
15}

1. 1

   gas=[1,2,3,4,5], cost=[3,4,5,1,2]. i=0: diff = 1−3 = −2. total=−2, tank=−2 < 0 → bỏ trạm 0, dời start = 1, tank = 0.

   i:0diff:-2total:-2tank:0start:1
2. 2

   i=1: diff = 2−4 = −2 → tank âm, dời start = 2. i=2: diff = 3−5 = −2 → tank âm, dời start = 3.

   (total đang = −6.)

   i:2total:-6tank:0start:3
3. 3

   i=3: diff = 4−1 = 3. total = −3, tank = 3 (≥ 0, không dời start). i=4: diff = 5−2 = 3. total = 0, tank = 6.

   i:4total:0tank:6start:3
4. 4

   Hết vòng: total = 0 ≥ 0 → có nghiệm, trả về start = 3.

   total:0start:3result:3