Precios tras el siguiente descuento
La misión
Problema
Una tienda lista los precios de sus artículos en el orden del estante. Comprar el artículo i da un descuento igual al precio del primer artículo a su derecha cuyo precio sea menor o igual que prices[i]. Si no existe ese artículo, no hay descuento. Devuelve el precio que realmente se paga por cada artículo.
Ejemplos
Input: prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]
Por qué: 8 tiene un descuento de 4, 4 y 6 tienen ambos un descuento de 2, y 2 y 3 no tienen ningún artículo más barato después
Input: prices = [10, 1, 1, 6]
Output: [9, 0, 1, 6]
Por qué: un precio igual cuenta, así que el primer 1 recibe el descuento del segundo 1
Input: prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Por qué: caso límite: con precios que suben, nunca aparece un artículo más barato a la derecha
Pistas
0 / 3
Para cada artículo necesitas el primer precio a su derecha que no sea mayor. Comparar cada artículo con todo lo que viene después es cuadrático. ¿Qué artículos siguen esperando su descuento en cada momento?
Un artículo deja de esperar en cuanto aparece un precio igual o menor que el suyo. Los artículos en espera siempre tienen precios que suben del fondo al tope, así que un precio nuevo los resuelve de arriba hacia abajo.
Mantén una pila de índices. Para cada precio nuevo, haz pop de cada índice cuyo precio sea mayor o igual que él y réstale el precio nuevo a ese artículo. Después haz push del nuevo índice. Los artículos que queden en la pila conservan su precio completo.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Solución
Este es el recorrido del siguiente elemento menor, el mismo que hace Largest Rectangle para encontrar dónde termina cada barra. Los índices esperan en una pila (stack) con precios crecientes, y el primer precio igual o menor que el de un artículo le hace pop y fija su descuento. Un artículo al que nunca se le hace pop no tenía ningún artículo más barato a su derecha, así que conserva su precio; por eso el resultado empieza como una copia de la entrada. Cada índice entra y sale de la pila como máximo una vez, así que el tiempo es O(n) y el espacio es O(n).
def final_prices(prices):
paid = prices[:] # no discount unless one is found
stack = [] # waiting indices, prices rising upward
for i, p in enumerate(prices):
while stack and prices[stack[-1]] >= p: # p is the first price at or below theirs
j = stack.pop()
paid[j] = prices[j] - p
stack.append(i)
return paid
print(final_prices([8, 4, 6, 2, 3])) # -> [4, 2, 4, 2, 3]
print(final_prices([10, 1, 1, 6])) # -> [9, 0, 1, 6]
print(final_prices([1, 2, 3, 4, 5])) # -> [1, 2, 3, 4, 5]¿Lo que te frena es la idea y no el código? Rectángulo más grande lo explica.