Pular para o conteúdo

Pilha com mínimo em tempo constante

Fácil#stack#auxiliary-stack~20 min

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

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

Travou na ideia, e não no código? Min Stack explica isso.

Python 3Ctrl+Enter executa