Estoy trabajando en el ejercicio de Stonewall de codility. Obtener el 100 % en las pruebas de corrección, pero reprobar todas las pruebas de rendimiento. Tengo problemas para imaginar por qué mi solución puede estar bien para entradas más pequeñas pero va tan mal para entradas más grandes. ¿Alguien puede ofrecer comentarios sobre lo que podría estar mal con mi solución? He encontrado este bastante desafiante. ¡Me tomó unos días volver a visitar solo para llegar a esta etapa! Gracias por adelantado.
El problema
Vas a construir un muro de piedra. El muro debe ser recto y de N metros de largo, y su espesor debe ser constante; sin embargo, debe tener diferentes alturas en diferentes lugares. La altura de la pared se especifica mediante una matriz H de N enteros positivos. H[I] es la altura del muro de I a I+1 metros a la derecha de su extremo izquierdo. En particular, H[0] es la altura del extremo izquierdo del muro y H[N−1] es la altura del extremo derecho del muro.
El muro debe construirse con bloques de piedra paralelepipédicos (es decir, todos los lados de dichos bloques son rectangulares). Tu tarea es calcular el número mínimo de bloques necesarios para construir el muro.
Escribe una función:
function solution(H);que, dada una matriz H de N enteros positivos que especifican la altura del muro, devuelve el número mínimo de bloques necesarios para construirlo.
Por ejemplo, dada la matriz H que contiene N = 9 enteros: H[0] = 8
H[1] = 8 H[2] = 5 H[3] = 7 H[4] = 9 H[5] = 8 H[6] = 7
H[7] = 4 H[8] = 8la función debería devolver 7. La figura muestra una disposición posible de siete bloques.
Escriba un algoritmo eficiente para las siguientes suposiciones:
N is an integer within the range [1..100,000]; each element of array H is an integer within the range [1..1,000,000,000].
Mi solución
function solution(H) { let stones = 0 let absoluteMinimum = Infinity; let prevStones = [] for (let i = 0; i < H.length; i++) { if (H[i] < absoluteMinimum) { stones ++ absoluteMinimum = H[i] prevStones = [H[i]] } else if (prevStones.includes(H[i])) { while (prevStones.includes(H[i])) { prevStones.pop() } prevStones.push(H[i]) } else if (H[i] != H[i-1]) { prevStones.push(H[i]) stones ++ } } return stones }Aquí está el resumen de mi intento, incluidos los resultados de las pruebas. https://app.codility.com/demo/results/training2V8Y42-AUQ/
Siguiendo el comentario de @Teemu, y teniendo en cuenta que el código simplemente busca en prevStones la existencia de una altura específica, sugiera crear otra matriz que contenga los recuentos de las alturas en prevStonesCount .
Por ejemplo, si establece prevStones = [ 8 ] , establezca prevStonesCount[ 8 ] = 1 , ya que hay una piedra en la matriz prevStones de altura 8.
Ahora, en lugar de tener que ejecutar prevStones.includes( 8 ) , simplemente verifique si 0 < prevStonesCount[ 8 ] . (Es decir, .includes() busca en toda la matriz prevStones una altura de 8, mientras que prevStonesCount[ 8 ] en un paso indica si hay piedras de altura 8 en la matriz prevStones ).
Por lo tanto, cada vez que realice un prevStones.push( x ) o prevStones.pop( x ) , realice el ajuste correspondiente de prevStonesCount[ x ] += 1 o prevStonesCount[ x ] -= 1 , respectivamente.
Tenga en cuenta también que dentro del primero if donde prevStones = [H[i]] , la matriz prevStones se borra esencialmente y se establece en un valor inicial. Esto significa que la matriz prevStonesCount también deberá borrarse y luego establecer prevStonesCount[ H[i] ] = 1 .