What is the best way to solve Gas Station?

The optimized O(n) approach using Greedy patterns is generally preferred.

상위 150개 인터뷰쉬움

주유소

'주유소' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

순환 경로를 따라 n개의 주유소가 있으며, i번째 주유소의 주유량은 gas[i]입니다. 당신은 무제한의 휘발유 탱크를 갖춘 자동차를 가지고 있고 i번째 역에서 다음 (i + 1)번째 역까지 이동하는 데 휘발유 비용이 듭니다. 주유소 중 한 곳에서 빈 탱크로 여행을 시작합니다. 시계 방향으로 한 바퀴를 돌 수 있으면 시작 주유소의 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다. 솔루션이 존재하는 경우 고유한 것으로 보장됩니다.

canCompleteCircuit(gas: List[int], cost: List[int]) -> int 함수를 작성하세요.

제약

•n == len(gas) == len(cost)
•1 <= n <= 10^5
•0 <= gas[i], cost[i] <= 10^4

예

Example 1

Input

gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output

Explanation

Start at station 3. tank = 4. Go to 4: cost 1, tank = 4-1+5 = 8. Go to 0: cost 2, tank = 8-2+1=7. Go to 1: cost 3, tank = 7-3+2=6. Go to 2: cost 4, tank = 6-4+3=5. Go to 3: cost 5, tank = 5-5=0. We reached back to station 3.

Example 2

Input

gas = [2,3,4], cost = [3,4,3]

Output

-1

Explanation

No station can complete the circuit.

Need a Hint?

세트나 힙과 같은 Greedy 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

Greedy 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def can_complete_circuit_opt(gas, cost):
    if sum(gas) < sum(cost): return -1
    total, start = 0, 0
    for i in range(len(gas)):
        total += gas[i] - cost[i]
        if total < 0: total = 0; start = i + 1
    return start

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def can_complete_circuit_brute(gas, cost):
    n = len(gas)
    for i in range(n):
        total = 0; can = True
        for j in range(n):
            idx = (i + j) % n
            total += gas[idx] - cost[idx]
            if total < 0: can = False; break
        if can: return i
    return -1