𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗶𝗮 𝟱: 𝗠𝗲𝗷𝗼𝗿 𝗺𝗼𝗺𝗲𝗻𝘁𝗼 𝗽𝗮𝗿𝗮 𝗰𝗼𝗺𝗽𝗿𝗮𝗿 𝘆 𝘃𝗲𝗻𝗱𝗲𝗿 𝗮𝗰𝗰𝗶𝗼𝗻𝗲𝘀

Leetcode 121 te pide encontrar el mejor momento para comprar y vender una acción. Recibes un array de precios. Cada índice representa un día. El valor es el costo en ese día.

El objetivo es sencillo. Comprar un día y vender en un día futuro para obtener el mayor beneficio. Si no es posible obtener beneficios, devuelve 0.

Restricciones del problema:

  • Longitud del array de hasta 100,000.
  • Precios de hasta 10,000.
  • Debes vender después de comprar.

Enfoque 1: El método ingenuo (Fuerza bruta)

El método de fuerza bruta comprueba cada par de compra y venta. Esto utiliza dos bucles.

  • Complejidad temporal: O(n²)
  • Problema: Es demasiado lento.

Si tienes 1,000 días, realizas 1,000,000 de comprobaciones. Si tienes 100,000 días, realizas 10,000,000,000 de comprobaciones. Esto provoca un timeout en Leetcode.

Enfoque 2: El método optimizado (Una sola pasada)

Puedes resolver esto en una sola pasada utilizando dos variables: minPrice y maxProfit.

  • Complejidad temporal: O(n)
  • Complejidad espacial: O(1)

Cómo funciona:

  1. Establece minPrice en Infinity.
  2. Establece maxProfit en 0.
  3. Recorre cada precio.
  4. Si el precio actual es menor que minPrice, actualiza minPrice.
  5. Si el precio actual menos minPrice es mayor que maxProfit, actualiza maxProfit.

Seguimiento del ejemplo con precios [7, 1, 5, 3, 6, 4]:

  • Día 1: Precio 7. minPrice pasa a ser 7. maxProfit se mantiene en 0.
  • Día 2: Precio 1. minPrice pasa a ser 1. maxProfit se mantiene en 0.
  • Día 3: Precio 5. 5 - 1 = 4. maxProfit pasa a ser 4.
  • Día 4: Precio 3. 3 - 1 = 2. maxProfit se mantiene en 4.
  • Día 5: Precio 6. 6 - 1 = 5. maxProfit pasa a ser 5.
  • Día 6: Precio 4. 4 - 1 = 3. maxProfit se mantiene en 5.

Respuesta final: 5.

La versión optimizada gana porque solo analiza cada precio una vez. Escala bien para conjuntos de datos grandes.

Fuente: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1