Dado un jardín con N ranuras. En cada ranura hay una flor. Cada una de las N flores florecerá una a una en N días. En cada día, habrá exactamente una flor floreciendo y seguirá floreciendo desde entonces.
Dada una matriz de números del 1 al N. Cada número de la matriz es la ranura donde la flor se abrirá en (i + 1) -ésimo día. Por ejemplo, la matriz [5, 3, 1, 4, 2] significa que el flujo 5 florecerá el día 1, la flor 3 florecerá el día 2, la flor 1 florecerá el día 3, etc.
Dado un número entero k, devuelve el primer día en el que existen dos flores floreciendo y también las flores entre ellas es k y estas flores no están floreciendo.
Solución Java 1
public int kEmptySlots(int[] flowers, int k) { int[] days = new int[flowers.length + 1]; for (int i = 0; i < flowers.length; i++) { days[flowers[i]] = i + 1; } int result = Integer.MAX_VALUE; for (int i = 1; i < days.length - k - 1; i++) { int l = days[i]; int r = days[i + k + 1]; int max = Math.max(l, r); int min = Math.min(l, r); boolean flag = true; for (int j = 1; j <= k; j++) { if (days[i + j] < max) { flag = false; break; } } if (flag && max < result) { result = max; } } return result == Integer.MAX_VALUE ? -1 : result; } |
La complejidad del tiempo es O (N * k) y la complejidad del espacio es O (N).
Solución Java 2
public int kEmptySlots2(int[] flowers, int k) { TreeSet<Integer> set = new TreeSet<>(); for (int i = 0; i < flowers.length; i++) { Integer higher = set.higher(flowers[i]); Integer lower = set.lower(flowers[i]); if (lower != null && flowers[i] - k - 1 == lower) { return i + 1; } if (higher != null && flowers[i] + k + 1 == higher) { return i + 1; } set.add(flowers[i]); } return -1; } |
La complejidad del tiempo es O (N * log (N)) y la complejidad del espacio es O (N).
