Pular para o conteúdo

Preços após o próximo desconto

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

A missão

Problema

Uma loja lista os preços dos itens na ordem da prateleira. Comprar o item i dá um desconto igual ao preço do primeiro item à direita dele cujo preço seja menor ou igual a prices[i]. Se esse item não existir, não há desconto. Retorne o preço efetivamente pago por cada item.

Exemplos

Input:  prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]
Por quê: 8 tem desconto de 4, 4 e 6 têm desconto de 2, e 2 e 3 não têm item mais barato depois deles
Input:  prices = [10, 1, 1, 6]
Output: [9, 0, 1, 6]
Por quê: um preço igual conta, então o primeiro 1 recebe desconto do segundo 1
Input:  prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Por quê: edge case: preços crescentes nunca encontram um item mais barato à direita

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(n)

Travou na ideia, e não no código? Maior retângulo explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado