Pilha com mínimo em tempo constante
A missão
Problema
Projete uma pilha que permita empilhar (push) um valor, desempilhar (pop) o valor do topo, ler o valor do topo e informar o menor valor armazenado no momento. Todas essas operações precisam rodar em tempo constante, então varrer o conteúdo para achar o mínimo não é aceitável. Você pode assumir que o mínimo só é pedido enquanto a pilha não está vazia.
Exemplos
Operations: push 5, push 2, push 7
minimum -> 2, top -> 7
Operations: pop, pop (starting from the stack above)
minimum -> 5, top -> 5
Por quê: desempilhar o 2 precisa restaurar o mínimo anterior
Operations: push 3, push 3, pop
minimum -> 3
Por quê: edge case: um mínimo duplicado precisa sobreviver a um desempilhamento
Dicas
0 / 3
Um único número guardando o mínimo quebra assim que esse mínimo é desempilhado, porque o mínimo anterior se perdeu. O histórico precisa ser guardado de alguma forma.
Repare que o mínimo só muda na hora de empilhar e de desempilhar, e muda na ordem “último a entrar, primeiro a sair”, exatamente como a própria pilha.
Junto com os valores, mantenha uma pilha paralela cujo topo sempre guarda o mínimo de tudo o que está abaixo do nível correspondente. Ao empilhar, guarde o menor entre o novo valor e o mínimo atual. Ao desempilhar, descarte o topo das duas pilhas juntas.
- Tempo-alvo
- O(1)
- Espaço-alvo
- O(n)
Restrições
- every operation runs in O(1) time
- minimum is only requested on a non-empty stack
Solução
Uma segunda pilha espelha a principal, guardando em cada nível o mínimo de tudo o que está nesse nível ou abaixo dele. Empilhar registra o menor entre o valor que chega e o mínimo anterior, então o topo do espelho é sempre a resposta. Desempilhar descarta os dois topos juntos, o que restaura o mínimo anterior automaticamente e trata mínimos duplicados corretamente. Toda operação é O(1) em tempo, e o espaço é O(n) para a pilha extra.
class MinStack:
def __init__(self): self.items, self.mins = [], [] # mins mirrors the running minimum
def push(self, x):
self.items.append(x)
# each level remembers the minimum of everything at or below it
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop() # both stacks always shrink together
return self.items.pop()
def top(self): return self.items[-1]
def minimum(self): return self.mins[-1]
s = MinStack()
for v in (5, 2, 7): s.push(v)
print(s.minimum(), s.top()) # -> 2 7
s.pop(); s.pop()
print(s.minimum(), s.top()) # -> 5 5Travou na ideia, e não no código? Min Stack explica isso.