Trạm Xăng Vòng TrònGas Station
Hiểu bài
Có n trạm xăng xếp thành vòng tròn. Tại trạm i đổ được gas[i] xăng; đi từ trạm i sang trạm kế tiếp tốn cost[i] xăng. Xe khởi hành với bình rỗng. Trả về chỉ số trạm xuất phát để chạy hết một vòng, hoặc -1 nếu không thể. Đề bảo đảm đáp án (nếu có) là duy nhất.
Ví dụ:
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
output = 3 // xuất phát từ trạm 3 thì chạy đủ một vòngXem cách cơ bản (chậm hơn)
O(n²) time, O(1) spacefunction canCompleteCircuit(gas: number[], cost: number[]): number {
const n = gas.length
for (let start = 0; start < n; start++) {
let tank = 0, ok = true
for (let step = 0; step < n; step++) {
const i = (start + step) % n
tank += gas[i] - cost[i]
if (tank < 0) { ok = false; break }
}
if (ok) return start
}
return -1
}Thử từng trạm làm điểm xuất phát rồi mô phỏng chạy hết vòng.
Đúng nhưng lặp lại rất nhiều phép tính — mỗi start chạy lại gần như cả vòng.
Lời giải tối ưu
O(n) time, O(1) spacefunction canCompleteCircuit(gas: number[], cost: number[]): number {
let total = 0 // tổng chênh lệch cả vòng
let tank = 0 // xăng tích luỹ kể từ start hiện tại
let start = 0
for (let i = 0; i < gas.length; i++) {
const diff = gas[i] - cost[i]
total += diff
tank += diff
if (tank < 0) { // không tới nổi trạm i+1 từ start hiện tại
start = i + 1
tank = 0
}
}
return total >= 0 ? start : -1
}Hai nhận xét tham lam:
- nếu tổng
gas< tổngcostthì chắc chắn vô nghiệm. - Nếu đi từ
startmà tới trạmibình âm, thì mọi trạm trong khoảng [start, i] đều không thể là điểm xuất phát — bỏ hết, thử lại từi+1
Một lượt quét là đủ vì đáp án (khi tồn tại) là duy nhất.
Chạy thử từng bước
- 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
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
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
Hết vòng: total = 0 ≥ 0 → có nghiệm, trả về start = 3.
total:0start:3result:3
Trường hợp biên phải nhớ
Tổng gas < tổng cost →
total < 0→ trả −1 dù tank ở cuối có thể vừa dương.Trạm cuối làm tank âm rồi dời start = n: nhờ kiểm tra
total >= 0cuối cùng nên vẫn trả đúng (start không bao giờ vượt thành chỉ số hợp lệ khi có nghiệm).gas = cost ở mọi trạm → total = 0, mọi điểm đều đi được; đáp án là start mặc định 0.
Một trạm duy nhất với gas[0] ≥ cost[0] → trả 0; ngược lại trả −1.