LeetCode – Candy (Java)

Hay N niños en fila. A cada niño se le asigna un valor de calificación. Estás regalando caramelos a estos niños sujetos a los siguientes requisitos:

1. Cada niño debe tener al menos un dulce.
2. Los niños con una calificación más alta obtienen más dulces que sus vecinos.

¿Cuál es el mínimo de caramelos que debes regalar?

Análisis

Este problema se puede resolver en O (n) tiempo.

Siempre podemos asignar a un vecino 1 más si el vecino tiene un valor de calificación más alto. Sin embargo, para obtener el número total mínimo, siempre debemos comenzar a agregar 1 en orden ascendente. Podemos resolver este problema escaneando la matriz desde ambos lados. Primero, escanee la matriz de izquierda a derecha y asigne valores para todos los pares ascendentes. Luego escanee de derecha a izquierda y asigne valores a pares descendentes.

Este problema es similar a Atrapar el agua de lluvia.

Solución Java

public int candy(int[] ratings) {
	if (ratings == null || ratings.length == 0) {
		return 0;
	}
 
	int[] candies = new int[ratings.length];
	candies[0] = 1;
 
	//from let to right
	for (int i = 1; i < ratings.length; i++) {
		if (ratings[i] > ratings[i - 1]) {
			candies[i] = candies[i - 1] + 1;
		} else { 
			// if not ascending, assign 1
			candies[i] = 1;
		}
	}
 
	int result = candies[ratings.length - 1];
 
	//from right to left
	for (int i = ratings.length - 2; i >= 0; i--) {
		int cur = 1;
		if (ratings[i] > ratings[i + 1]) {
			cur = candies[i + 1] + 1;
		}
 
		result += Math.max(cur, candies[i]);
		candies[i] = cur;
	}
 
	return result;
}