Estoy tratando de resolver la pregunta Sum of Subarray Ranges de subarray en leetcode, me está dando Time Limit Exceeded , así que supongo que mi código no está bien optimizado y necesita soluciones más eficientes. Pero no soy tan bueno en eso, así que para ser específico, ¿cómo puedo eliminar dos for-loops con uno en mi código?
Ques1: Sum of Subarray Ranges
Se le da una matriz de números enteros. El rango de un subarreglo de números es la diferencia entre el elemento más grande y el más pequeño del subarreglo. Devuelve la suma de todos los rangos de subarreglo de nums. Un subarreglo es una secuencia contigua no vacía de elementos dentro de un arreglo.
Ejemplo:
Input: nums = [1,2,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [2], range = 2 - 2 = 0 [3], range = 3 - 3 = 0 [1,2], range = 2 - 1 = 1 [2,3], range = 3 - 2 = 1 [1,2,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.enlace de preguntas
Mi código: Casos de prueba: 52/71
var subArrayRanges = function(nums) { let maxSub=0; for(let i=0; i<nums.length; i++){ let arr=[]; arr.push(nums[i]) for(let j=i+1; j<nums.length; j++){ arr.push(nums[j]); maxSub=maxSub+(Math.max(...arr)) - (Math.min(...arr)); } } return maxSub };¿Cómo puedo optimizar mi código para que pueda ejecutar todos los casos de prueba?
Una sugerencia para la parte de optimización: cuando j -loop obtiene un nuevo elemento, solo ese elemento puede afectar el mínimo/máximo del subarreglo dado. Por lo tanto, en realidad no tiene que construir el subarreglo y ejecutar llamadas min() / max() reales en él, solo almacene sus valores mínimo y máximo (que son el mismo elemento [i] al comienzo del ciclo interno) y compárelos+actualícelos usando el nuevo elemento entrante (el [j] ):
var subArrayRanges = function(nums) { let maxSub=0; for(let i=0; i<nums.length; i++){ let min=nums[i],max=nums[i]; for(let j=i+1; j<nums.length; j++){ if(nums[j]<min)min=nums[j]; if(nums[j]>max)max=nums[j]; maxSub=maxSub+max-min; } } return maxSub };