LeetCode – Gasolinera (Java)

Hay N gasolineras a lo largo de una ruta circular, donde la cantidad de gasolina en la estación i es gas[i].

Tienes un carro con tanque de gasolina ilimitado y cuesta costo[i] de gas para viajar desde la estación i a la siguiente estación (i + 1). Comienzas el viaje con un tanque vacío en una de las estaciones de servicio.

Devuelve el índice de la gasolinera inicial si puedes recorrer el circuito una vez; de lo contrario, devuelve -1.

Análisis

Para resolver este problema, debemos comprender y utilizar los siguientes 2 hechos:
1) si la suma del gas> = la suma del costo, entonces el círculo se puede completar.
2) si A no puede llegar a C en la secuencia de A -> B -> C, entonces B tampoco puede hacerlo.

Prueba de hecho 2:

If gas[A] < cost[A], then A can not even reach B. 
So to reach C from A, gas[A] must >= cost[A]. 
Given that A can not reach C, we have gas[A] + gas[B] < cost[A] + cost[B],
and gas[A] >= cost[A],
Therefore, gas[B] < cost[B], i.e., B can not reach C. 

En la siguiente solución, sumRemaining realiza un seguimiento de la suma del resto del índice actual. Si sumRemaining <0, entonces cada índice entre el inicio anterior y el índice actual es malo, y debemos actualizar el inicio para que sea el índice actual. Puede utilizar el siguiente ejemplo para visualizar la solución.

Solución Java

public int canCompleteCircuit(int[] gas, int[] cost) {
	int sumRemaining = 0; // track current remaining
	int total = 0; // track total remaining
	int start = 0; 
 
	for (int i = 0; i < gas.length; i++) {
		int remaining = gas[i] - cost[i];
 
		//if sum remaining of (i-1) >= 0, continue 
		if (sumRemaining >= 0) { 
			sumRemaining += remaining;
		//otherwise, reset start index to be current
		} else {
			sumRemaining = remaining;
			start = i;
		}
		total += remaining;
	}
 
	if (total >= 0){
		return start;
	}else{
		return -1;
	}
}