Problema
Uno Stack<T> generico funziona per qualsiasi tipo. Qui estendi l'idea: uno stack di interi che può anche restituire il suo minimo in tempo costante.
Elabora le operazioni in ordine:
push <x>: aggiungi x in cima allo stack.pop: rimuovi il valore in cima (ignorato quando lo stack è vuoto).min: restituisci il valore più piccolo attualmente nello stack, oppure -1 se è vuoto.
Implementa min_stack_operations(operations).
Input
operations: Le operazioni.
Output
Restituisci le risposte delle operazioni min, nell'ordine.
Vincoli
1 ≤ numero di operazioni ≤ 200,000
0 ≤ x ≤ 10^9
Esempi
Input:
operations = ["push 5", "push 3", "min", "pop", "min"]
Output atteso:
expected = [3, 5]Input:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
Output atteso:
std::vector<long long> expected = {3, 5};Input:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
Output atteso:
long[] expected = new long[] {3, 5};Spiegazione
Con 5 e 3 nello stack il minimo è 3. Dopo aver rimosso 3, resta solo 5: [3, 5].
Input:
operations = ["min", "pop", "push 7", "min"]
Output atteso:
expected = [-1, 7]Input:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
Output atteso:
std::vector<long long> expected = {-1, 7};Input:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
Output atteso:
long[] expected = new long[] {-1, 7};Spiegazione
Lo stack vuoto restituisce -1 e il pop viene ignorato; poi il minimo è 7: [-1, 7].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Accanto a ogni valore, salva il minimo dello stack in quel momento.
Suggerimento 2
Il minimo attuale è allora semplicemente la cima di questo secondo stack.
Suggerimento 3
Ignora pop sullo stack vuoto e rispondi -1 a min quando è vuoto.
Complessità attesa
tempo O(numero di operazioni), spazio aggiuntivo O(numero di operazioni)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.