Min Stack
Projete uma pilha que, além das operações usuais push, pop e top, possa informar o menor valor que contém com getMin. Cada uma das quatro operações deve ser executada em tempo O(1).
Você recebe as operações em ordem como ops, com args[i] contendo o valor para um push e 0 para todas as outras operações. Execute-as em uma única pilha que começa vazia e retorne uma string por operação: "null" para push e pop, e o número como texto para top e getMin.
Função
- opsstring-array
- as operações, na ordem em que são executadas
- argsinteger-array
- o valor de cada push, 0 para todas as outras operações
- Retornastring-array
- uma resposta por operação, como texto
Restrições
1 ≤ ops.length ≤ 3000args.length == ops.length- Todo
ops[i]épush,pop,topougetMin. -231+1 ≤ args[i] ≤ 231-1para um push, eargs[i] == 0para qualquer outra operação.pop,topegetMinsó são chamados quando a pilha contém pelo menos um valor.
Exemplos
- Entrada
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- Saída
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- Explicação
- A pilha contém 4, 1 e 7, de baixo para cima, então o menor valor é 1. Remover 7 deixa 1 no topo. Remover 1 também deixa apenas 4, então o mínimo volta a ser 4.
- Entrada
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- Saída
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- Explicação
- O mínimo, -2, é inserido duas vezes. O primeiro pop remove uma cópia, e a outra ainda está lá, então
getMincontinua sendo -2. Só depois do segundo pop o mínimo volta a ser 3.
- Entrada
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- Saída
- ["null", "null", "null", "null", "2", "8"]
- Explicação
- 0 é empilhado e desempilhado novamente, então deixa de contar. A pilha passa a conter 2 e 8: o topo é 8 e o mínimo é 2.
+16 testes ocultos ao enviar
Para ir além
Você consegue criar uma fila do tipo primeiro a entrar, primeiro a sair que também informe seu mínimo em tempo amortizado O(1)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Uma variável que armazena o mínimo funciona até você remover esse mínimo. O que você precisaria saber nesse momento e quando poderia ter anotado isso?
Uma pilha só muda no topo, então o menor dos valores abaixo de qualquer altura permanece o mesmo enquanto essa altura estiver preenchida. Registre o mínimo ao empilhar.
Mantenha uma segunda pilha ao lado dos valores. Empilhe nela quando o novo valor for menor ou igual ao seu topo e desempilhe dela quando o valor que sair da pilha principal for igual ao seu topo. O topo dela será então sempre a resposta de
getMin.
Solução
Uma pilha simples já executa push, pop e top em O(1); a parte difícil é manter o mínimo após remoções. O fato principal é que uma pilha só muda no topo: enquanto um valor está em determinada altura, nada abaixo dele pode mudar, então o mínimo de tudo até essa altura é fixo. Anote esse mínimo ao inserir, e uma remoção restaura o anterior sem custo adicional. As abordagens diferem no que anotam.
Examine a pilha a cada getMin
Intuição
Use uma pilha comum para push, pop e top, e responda a getMin examinando todos os valores que ela contém e mantendo o menor. Isso está sempre correto, porque verifica o conteúdo real no momento da chamada.
Isso viola o requisito O(1). Uma chamada de getMin em uma pilha com n valores lê todos os n valores. O teste oculto que empilha 1.500 valores com uma chamada de getMin após cada inserção lê cerca de 1.500 × 1.500 / 2, mais de um milhão de valores, enquanto as outras abordagens leem um por chamada. Um sistema que executa 10^5 dessas operações leria bilhões de valores.
Manter um único mínimo em cache não resolve. Uma variável que armazena o menor valor funciona para inserções, mas, depois que esse valor é removido da pilha, não é possível saber qual é o próximo menor sem fazer outra varredura.
Algoritmo
- Armazene os valores em uma lista usada como pilha.
- Para
push x, adicionex; parapop, remova o último valor; paratop, leia-o. - Para
getMin, percorra todos os valores armazenados e retorne o menor. - Registre cada resposta como texto e retorne a lista.
class MinStack:
def __init__(self):
self.values = []
def push(self, x):
self.values.append(x)
def pop(self):
self.values.pop()
def top(self):
return self.values[-1]
def getMin(self):
# Look at every stored value: O(n).
smallest = self.values[0]
for v in self.values:
if v < smallest:
smallest = v
return smallest
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return resultArmazene o mínimo ao lado de cada valor
Intuição
Enquanto um valor estiver na altura i da pilha, os valores abaixo dele não podem mudar, então o menor dos i valores de baixo permanece fixo enquanto esse valor estiver ali. Armazene esse número ao lado de cada valor: uma segunda pilha mins em que mins[i] é o menor de values[0..i].
Ao empilhar, a nova entrada de mins é o menor entre x e a entrada abaixo dela. Ao desempilhar, remova o topo de ambas as pilhas; o topo de mins volta a ser o mínimo do que restou. getMin lê o topo de mins.
No primeiro exemplo, os valores empilhados 4, 1 e 7 armazenam os mínimos 4, 1 e 1. Desempilhar 7 deixa 1 no topo de mins, e desempilhar 1 deixa 4. Cada operação toca apenas os topos de duas pilhas, então cada uma é O(1). O custo é armazenar um segundo número para cada valor.
Algoritmo
- Mantenha duas pilhas com a mesma altura,
valuesemins. - Para
push x, empilhexemvaluese empilhe o menor entrexe o topo deminsemmins(o próprioxseminsestiver vazia). - Para
pop, desempilhe ambas as pilhas. - Para
top, leia o topo devalues; paragetMin, leia o topo demins. - Registre cada resposta como texto e retorne a lista.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # mins[i] is the smallest of values[0..i]
def push(self, x):
self.values.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.values.pop()
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return resultUma pilha de mínimos que cresce somente quando surge um novo mínimo
Intuição
Na segunda abordagem, mins costuma se repetir: empilhe 1 e depois 7, 8 e 9, e mins contém 1, 1, 1, 1. Uma entrada repetida não traz nenhuma informação nova. Portanto, registre um valor em mins somente quando ele se tornar o mínimo, e remova-o quando esse mesmo valor sair de values.
Ao empilhar, adicione x a mins se mins estiver vazio ou se x for menor ou igual ao topo. Ao desempilhar, se o valor que sai de values for igual ao topo de mins, desempilhe mins também. O topo de mins é sempre o mínimo atual: todo valor empilhado depois dele é maior ou, se era menor ou igual a ele, também foi registrado e foi desempilhado desde então.
A comparação deve ser <=, não <. No segundo exemplo, -2 é empilhado duas vezes. Com <, somente a primeira ocorrência é registrada; o primeiro desempilhamento a remove de mins, e getMin retorna 3 enquanto ainda há um -2 na pilha. Com <=, cada ocorrência recebe sua própria entrada.
As quatro operações continuam sendo O(1). Quando os valores chegam do maior para o menor, mins cresce até ficar tão alto quanto values; quando o mínimo raramente muda, ele permanece pequeno.
Algoritmo
- Mantenha uma pilha
valuese uma pilhamins. - Para
push x, empilhexemvalues. Seminsestiver vazia ouxfor menor ou igual ao elemento do topo, empilhextambém emmins. - Para
pop, desempilhevalues. Se o valor removido for igual ao elemento do topo demins, desempilheminstambém. - Para
top, leia o elemento do topo devalues; paragetMin, leia o elemento do topo demins. - Registre cada resposta como texto e retorne a lista.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # each value that was a minimum when pushed; the top is the current minimum
def push(self, x):
self.values.append(x)
# <= keeps one copy per equal minimum, so popping one leaves the others.
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
if self.values.pop() == self.mins[-1]:
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result
Armadilhas e casos extremos
Os bugs aqui dizem respeito às cópias do mínimo e ao que uma operação de pop remove.
- Registrar um novo mínimo apenas quando
xfor estritamente menor. Assim, uma segunda cópia do mínimo não é incluída emmins, e remover a primeira cópia faz com que o mínimo se perca, embora a segunda ainda esteja na pilha. O segundo exemplo detecta isso. - Manter o mínimo em uma variável. Isso funciona para inserções, mas, depois que o mínimo é removido, a variável fica desatualizada, e encontrar o próximo menor exige uma varredura.
- Comparar inteiros empacotados por referência. Em Java,
Integer == Integerverifica se ambos são o mesmo objeto. Isso acontece com valores de -128 a 127, que Java armazena em cache, e falha para a maioria dos valores maiores; por isso, a verificação da remoção falha apenas com valores grandes. Primeiro, converta paraint, como faz o código Java. - Remover de
minsem toda operação de pop na terceira abordagem. Ela só diminui quando o valor removido está no topo; na segunda abordagem, as duas pilhas sempre avançam juntas. - Retornar um número para
pop. Neste formato,popretorna"null", assim comopush.
Perguntas frequentes4
Como obter o mínimo de uma pilha em tempo O(1)?
Registre o mínimo no momento da inserção. Uma pilha só muda no topo, então o mínimo dos valores abaixo de qualquer altura não pode mudar enquanto essa altura estiver preenchida. Mantenha uma segunda pilha com o mínimo em cada altura, ou apenas cada novo mínimo, e getMin se torna uma leitura do topo.
Por que adicionar à pilha de mínimo quando o valor é igual ao mínimo atual?
Porque o mínimo pode estar na pilha mais de uma vez. Se você registrar apenas valores estritamente menores, duas cópias de -2 compartilham uma entrada em mins. A primeira remoção de -2 elimina essa entrada, e getMin então informa o mínimo antigo, embora o segundo -2 ainda esteja lá. Registrar valores iguais dá a cada cópia sua própria entrada.
É possível implementar uma pilha mínima com espaço extra O(1)?
Sim, com uma pilha e uma variável min. Quando você empilha um x menor que o mínimo atual, armazene 2x - min em vez disso e defina min = x; o número armazenado fica então menor que min, o que o marca. Quando um número marcado é desempilhado, o mínimo anterior é 2 * min - stored. A aritmética excede os limites de inteiros de 32 bits perto dos extremos, então são necessários valores de 64 bits, e a lógica dos sinais é propensa a erros; a maioria dos entrevistadores fica satisfeita com a versão de duas pilhas.
Qual é a complexidade de tempo e espaço da Min Stack?
Cada operação é O(1): push, pop, top e getMin leem ou alteram apenas o topo de uma ou duas pilhas. O espaço é O(n) para n valores armazenados. Armazenar o mínimo ao lado de cada valor sempre usa 2n posições; armazenar apenas os novos mínimos usa entre n + 1 e 2n.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def minStackOps(ops, args):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
Esperado
["null", "null", "null", "1", "null", "1", "null", "4"]