Saltar al contenido

Precios tras el siguiente descuento

Fácil#monotonic-stack#next-smaller~15 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(n)

¿Lo que te frena es la idea y no el código? Rectángulo más grande lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio