Best Time to Buy and Sell Stock
Recibes una lista prices, donde prices[i] es el precio de una acción el día i. Puedes comprar una acción un día y venderla en un día posterior. Devuelve la mayor ganancia que puedas obtener, o 0 cuando todas las operaciones posibles den pérdidas.
Función
- pricesinteger-array
- el precio de la acción cada día, en orden
- Devuelveinteger
- la mayor ganancia de una compra y una venta posterior, o 0
Restricciones
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- Realizas como máximo una operación y vendes en un día posterior al de la compra.
Ejemplos
- Entrada
- prices = [7, 2, 5, 9, 1, 4]
- Salida
- 7
- Explicación
- Compra el día 1 a 2 y vende el día 3 a 9 para obtener una ganancia de 7. El precio más bajo, 1 el día 4, viene después del 9, así que la mejor venta posterior solo genera 3.
- Entrada
- prices = [9, 7, 4, 3, 1]
- Salida
- 0
- Explicación
- El precio baja todos los días, así que cada venta sería inferior al precio de compra. No haces ninguna operación, y la ganancia es 0.
Para ir más allá
¿Y si pudieras realizar tantas operaciones como quisieras, pero manteniendo como máximo una acción a la vez?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
La venta siempre viene después de la compra. Elige un día para vender: ¿qué día de compra genera más ganancias?
Para un día de venta determinado, el mejor día para comprar es el día más barato anterior. No tienes que volver a buscar ese día cada vez si lo recuerdas mientras avanzas.
Recorre los días en orden y lleva la cuenta de dos números: el precio más bajo hasta el momento y la mejor ganancia hasta el momento. Cada día, compara el precio de hoy menos el precio más bajo con la mejor ganancia y, después, actualiza el precio más bajo.
Solución
Debes comprar antes de vender, así que la respuesta no es el precio más alto menos el más bajo. Para cada día en que podrías vender, la mejor compra es el día más barato anterior. Mantener ese precio más bajo mientras avanzas convierte el problema en un solo recorrido.
Prueba cada par de compra y venta
Correcto, pero no termina con las pruebas más grandes
Intuición
Cada operación tiene un día de compra y un día posterior de venta, así que prueba cada par y conserva la mayor diferencia. Empezar con la mejor ganancia en 0 cubre la opción de no operar. Se comprueban todas las operaciones permitidas, así que la respuesta es correcta.
Una lista de n precios tiene aproximadamente n²/2 pares: 100 000 días significa unos 5 mil millones de restas.
Algoritmo
- Establece
besten 0. - Recorre cada día de compra
buy. - Para cada uno, recorre cada día de venta
sellposterior. - Calcula
prices[sell]menosprices[buy]y guárdalo enbestsi es mayor. - Devuelve
best.
def maxProfit(prices):
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n):
best = max(best, prices[sell] - prices[buy])
return best
Una pasada con el precio más bajo hasta ahora
Intuición
Fija el día de venta i. El mejor día para haber comprado es el día más barato hasta i, así que la mejor operación que termina el día i gana prices[i] menos el precio más bajo hasta ese momento. Cada día de venta se empareja con su mejor día de compra, así que la mayor de esas ganancias es la respuesta. En un día que establece un nuevo mínimo, la ganancia es 0, igual que si no se operara.
El recorrido lee cada precio una vez y mantiene dos números, lowest y best: tiempo O(n) y espacio O(1).
Algoritmo
- Establece
lowesten el primer precio ybesten 0. - Recorre los precios en orden.
- Si el precio actual es menor que
lowest, conviértelo en el nuevolowest. - Calcula el precio actual menos
lowesty guárdalo enbestsi es mayor. - Devuelve
best.
def maxProfit(prices):
lowest = prices[0]
best = 0
for price in prices:
if price < lowest:
lowest = price
elif price - lowest > best:
best = price - lowest
return best
Errores comunes y casos límite
- Devolver el precio más alto menos el precio más bajo. En
[7, 2, 5, 9, 1, 4]eso da 8, pero el 1 aparece después del 9. La respuesta es 7. - Permitir que la respuesta sea negativa. En
[9, 7, 4, 3, 1]la mejor diferencia es -1; inicializabesten 0, no en la primera diferencia. - Inicializar
lowesten 0. Entonces, cada ganancia equivale al precio mismo, así que[9, 7, 4, 3, 1]devuelve 9. Inicialízalo con el primer precio.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Best Time to Buy and Sell Stock?
La solución de una sola pasada tarda O(n) para n días, porque lee cada precio una vez, y usa O(1) de espacio adicional: el precio más bajo hasta el momento y la mejor ganancia. Probar cada par de días tarda O(n²).
¿Por qué no restar el precio más bajo del más alto?
El precio más bajo puede venir después del más alto, y debes comprar antes de vender. En [7, 2, 5, 9, 1, 4], el 1 viene después del 9, así que la mejor operación permitida compra a 2 y vende a 9 para obtener 7.
¿Es «Best Time to Buy and Sell Stock» un problema de programación dinámica?
Puedes leerlo de cualquiera de las dos maneras. El precio más bajo hasta ahora es un pequeño estado que actualizas cada día, que es la perspectiva de programación dinámica. Emparejar cada venta con el día anterior más barato es la perspectiva voraz. Ambas conducen al mismo código de una sola pasada.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def maxProfit(prices):
# Escribe el código aquíPrueba #1
Prueba #2
Argumento
prices = [7, 2, 5, 9, 1, 4]
Salida Esperada
7