Estoy tratando de encontrar una solución para este problema, en JavaScript, con una complejidad de tiempo O (N).
Problema: Te dan una matriz A de N enteros positivos y un entero k. Desea eliminar k elementos consecutivos de A de modo que la amplitud del elemento restante sea mínima. La amplitud es la diferencia entre los elementos mínimo y máximo.
For eg. A[] = [8,7,4,1] and k=2. Output should be 1 because we will remove 4 and 1.
Una solución de fuerza bruta es simple. ¿Es posible hacerlo en O(n)? Gracias
¿Esto te ayuda? Primero determino los 3 números más grandes (3 porque quitamos 2 números consecutivos y es posible que esos 2 números sean los 2 más grandes, entonces necesitamos el siguiente más grande), luego hacemos lo mismo para los 3 números más pequeños.
Creamos una matriz de los números consecutivos eliminados, sin alterar la matriz original.
Luego simplemente ejecutamos algunas declaraciones if else para determinar si el máximo, el mínimo está contenido en los números consecutivos eliminados
Aunque no es el más bonito. Mucho si/si no
const arr = [8, 7, 4, 1] const arr2 = [8, 7, 4, 1, 4, 6, 8] const arr3 = [8, 7, 4, 1, 4, 6, 8, 3, 11, 4, 15] function slice2Consecutive(arr) { let newArr = [] for (let i = 0; i < arr.length - 1; i++) { let s1 = arr[i] let s2 = arr[i + 1] newArr.push([arr[i], arr[i + 1]]) } return newArr } function maxThree(arr) { let one = -Infinity; let two = -Infinity; let three = -Infinity; for (let i = 0; i < arr.length; i += 1) { let num = arr[i]; if (num > three) { if (num >= two) { three = two; if (num >= one) { two = one; one = num; } else { two = num; } } else { three = num; } } } return [one, two, three] } function minThree(arr) { let one = +Infinity; let two = +Infinity; let three = +Infinity; for (let i = 0; i < arr.length; i += 1) { let num = arr[i]; if (num < three) { if (num <= two) { three = two; if (num <= one) { two = one; one = num; } else { two = num; } } else { three = num; } } } return [one, two, three] } function minAmplitude(arr) { const [max, secondMax, thirdMax] = maxThree(arr) const [min, secondMin, thirdMin] = minThree(arr) const slicedArr = slice2Consecutive(arr) const amplitudeArr = [] for (let i = 0; i < slicedArr.length; i++) { let m = max let n = min if (slicedArr[i][0] === max || slicedArr[i][1] === max) { if (slicedArr[i][0] === secondMax || slicedArr[i][1] === secondMax) { m = thirdMax } else { m = secondMax } } if (slicedArr[i][0] === min || slicedArr[i][1] === min) { if (slicedArr[i][0] === secondMin || slicedArr[i][1] === secondMin) { n = thirdMin } else { n = secondMin } } amplitudeArr.push(m - n) } return Math.min(...amplitudeArr) } console.log(minAmplitude(arr)) console.log(minAmplitude(arr2)) console.log(minAmplitude(arr3))