Preços após o próximo desconto
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
Para cada item, você precisa do primeiro preço à direita dele que não seja maior. Comparar cada item com tudo o que vem depois é quadrático. Quais itens ainda estão esperando o desconto em um dado momento?
Um item para de esperar assim que aparece um preço igual ou menor que o dele. Os itens em espera sempre têm preços crescentes da base para o topo, então um preço novo os resolve de cima para baixo.
Mantenha uma pilha de índices. Para cada preço novo, desempilhe (pop) todo índice cujo preço seja maior ou igual a ele e subtraia o preço novo desse item. Depois, empilhe (push) o novo índice. Os itens que sobram na pilha mantêm o preço cheio.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Solução
Esta é a varredura do próximo elemento menor, a mesma que o Largest Rectangle faz para descobrir onde cada barra para. Os índices esperam em uma pilha com preços crescentes, e o primeiro preço igual ou menor que o de um item o desempilha e fixa o desconto dele. Um item que nunca é desempilhado não tinha item mais barato à direita, então mantém o preço, e é por isso que o resultado começa como uma cópia da entrada. Cada índice é empilhado e desempilhado no máximo uma vez, então o tempo é O(n) e o espaço é 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]Travou na ideia, e não no código? Maior retângulo explica isso.