134. Gas Station
Tags:
Medium
Skills:
Array
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm một trạm xăng xuất phát (index) sao cho nếu bắt đầu từ đó, bạn có thể đi hết một vòng qua tất cả các trạm mà không bị hết xăng giữa đường. Nếu không có trạm nào thỏa mãn, return -1
Approach
sum(gas) ) < tổng chi phí (sum(cost) ), chắc chắn không thể hoàn thành vòng tròn, return -1 ngayThuật toán Greedy
gas[i] - cost[i] cộng dồn vào biến curr_tank curr_tank< 0 tại vị trí i, reset curr_tank = 0 và chọn điểm xuất phát mới là i + 1total_tank ) ≥ 0, return điểm xuất phát, ngược lại return -1Solution
1function canCompleteCircuit(gas: number[], cost: number[]): number {
2 let total_tank = 0;
3 let curr_tank = 0;
4 let start = 0
5 for (let i = 0; i < gas.length; i++) {
6 total_tank += gas[i] - cost[i];
7 curr_tank += gas[i] - cost[i];
8 if (curr_tank < 0) {
9 start = i + 1
10 curr_tank = 0
11 }
12 }
13 return total_tank >= 0 ? start : -1
14};Khi bạn đi từ điểm xuất phát hiện tại (giả sử là start ) đến trạm i , nếu tại i lượng xăng trong bình bị âm curr_tank < 0 , điều này có nghĩa là bất kỳ điểm nào xuất phát vào giữa start -> i cùng đều không thể hoàn thành vòng tròn. Do đó, bạn phải thử xuất phát từ trạm kết tiếp, tức là i + 1
Diễn giải chi tiết
Giả sử bạn thử xuất phát từ start, đi qua các trạm start, start+1, ..., i, và tại trạm i, lượng xăng trong bình bị âm.
start+1, thì lượng xăng tích lũy sẽ còn thấp hơn so với xuất phát từ start (vì bạn bỏ qua lượng gas và cost ở trạm start), nên chắc chắn cũng sẽ bị âm trước hoặc tại i.start+2, ..., i.i + 1.