Problema
Uma Stack<T> genérica funciona para qualquer tipo. Aqui você estende a ideia: uma pilha de inteiros que também pode informar seu mínimo em tempo constante.
Processe as operações na ordem:
push <x>: empilha x.pop: remove o valor do topo (ignorado quando a pilha está vazia).min: informa o menor valor atualmente na pilha, ou -1 se ela estiver vazia.
Implemente min_stack_operations(operations).
Input
operations: As operações.
Output
Retorne as respostas das operações min, na ordem.
Restrições
1 ≤ número de operações ≤ 200,000
0 ≤ x ≤ 10^9
Exemplos
Entrada:
operations = ["push 5", "push 3", "min", "pop", "min"]
Saída esperada:
expected = [3, 5]Entrada:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
Saída esperada:
std::vector<long long> expected = {3, 5};Entrada:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
Saída esperada:
long[] expected = new long[] {3, 5};Explicação
Com 5 e 3 na pilha, o mínimo é 3. Após remover 3, sobra apenas 5: [3, 5].
Entrada:
operations = ["min", "pop", "push 7", "min"]
Saída esperada:
expected = [-1, 7]Entrada:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
Saída esperada:
std::vector<long long> expected = {-1, 7};Entrada:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
Saída esperada:
long[] expected = new long[] {-1, 7};Explicação
A pilha vazia retorna -1 e o pop é ignorado; então o mínimo é 7: [-1, 7].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Ao lado de cada valor, guarde o mínimo da pilha naquele momento.
Dica 2
Assim o mínimo atual é simplesmente o topo dessa segunda pilha.
Dica 3
Ignore pop com a pilha vazia e responda -1 para min quando estiver vazia.
Complexidade esperada
tempo O(número de operações), espaço extra O(número de operações)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.