Min Stack
Progetta una pila che, oltre alle consuete operazioni push, pop e top, possa restituire il valore più piccolo che contiene con getMin. Ciascuna delle quattro operazioni deve essere eseguita in tempo O(1).
Ricevi le operazioni in ordine come ops, con args[i] che contiene il valore per un'operazione push e 0 per ogni altra operazione. Eseguile su un'unica pila inizialmente vuota e restituisci una stringa per ogni operazione: "null" per push e pop, e il numero sotto forma di testo per top e getMin.
Funzione
- opsstring-array
- le operazioni, nell’ordine in cui vengono eseguite
- argsinteger-array
- il valore per ogni push, 0 per ogni altra operazione
- Restituiscestring-array
- una risposta per operazione, come testo
Vincoli
1 ≤ ops.length ≤ 3000args.length == ops.length- Ogni
ops[i]èpush,pop,topogetMin. -231+1 ≤ args[i] ≤ 231-1per un'operazione push, eargs[i] == 0per qualsiasi altra operazione.pop,topegetMinvengono chiamate solo quando lo stack contiene almeno un valore.
Esempi
- Input
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- Output
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- Spiegazione
- Lo stack contiene 4, 1 e 7 dal basso verso l’alto, quindi il più piccolo è 1. Rimuovere 7 lascia 1 in cima. Rimuovere anche 1 lascia solo 4, quindi il minimo torna a 4.
- Input
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- Output
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- Spiegazione
- Il minimo, -2, viene inserito due volte. La prima rimozione ne elimina una copia e l'altra è ancora presente, quindi
getMinrimane -2. Solo dopo la seconda rimozione il minimo torna a 3.
- Input
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- Output
- ["null", "null", "null", "null", "2", "8"]
- Spiegazione
- 0 viene inserito e poi rimosso di nuovo, quindi non viene più conteggiato. Nello stack restano 2 e 8: in cima c’è 8 e il minimo è 2.
+16 test nascosti all’invio
Per approfondire
Riesci a creare una coda FIFO che restituisca anche il suo minimo in tempo ammortizzato O(1)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Una variabile che contiene il minimo funziona finché non estrai quel minimo. Che cosa dovresti sapere in quel momento e quando avresti potuto annotarlo?
Uno stack cambia solo nella parte superiore, quindi il più piccolo dei valori sotto qualsiasi altezza rimane invariato finché quell’altezza è occupata. Registra il minimo quando esegui un push.
Tieni una seconda pila accanto ai valori. Inserisci un elemento in cima quando il nuovo valore è minore o uguale al suo elemento superiore, e rimuovilo quando il valore che esce dalla pila principale è uguale al suo elemento superiore. L'elemento in cima è quindi sempre la risposta a
getMin.
Soluzione
Una pila semplice esegue già push, pop e top in O(1); la parte difficile è mantenere un minimo che sopravviva alle operazioni di rimozione. Il fatto fondamentale è che una pila cambia solo in cima: finché un valore si trova a una certa altezza, nulla al di sotto può cambiare, quindi il minimo di tutti gli elementi fino a quell’altezza rimane fisso. Annotalo quando inserisci un elemento e un’operazione di rimozione ripristinerà gratuitamente il minimo precedente. Gli approcci differiscono per ciò che annotano.
Esamina la pila a ogni getMin
Intuizione
Usa una normale pila per push, pop e top, e rispondi a getMin esaminando ogni valore che contiene e mantenendo il più piccolo. È sempre corretto, perché controlla il contenuto effettivo al momento della chiamata.
Questo viola il requisito O(1). Un getMin su una pila di n valori li legge tutti. Il test nascosto, che inserisce 1,500 valori con un getMin dopo ogni inserimento, ne legge circa 1,500 × 1,500 / 2, oltre un milione, mentre gli altri approcci ne leggono uno per chiamata. Un sistema che esegue 10^5 operazioni di questo tipo ne leggerebbe miliardi.
Una sola variabile che memorizza il minimo non risolve il problema. Una variabile che contiene il valore più piccolo funziona per gli inserimenti, ma quando quel valore viene rimosso non puoi sapere quale sia il successivo più piccolo senza eseguire di nuovo una scansione.
Algoritmo
- Memorizza i valori in una lista usata come stack.
- Per
push x, aggiungix; perpop, rimuovi l'ultimo valore; pertop, leggilo. - Per
getMin, esamina ogni valore memorizzato e restituisci il più piccolo. - Registra ogni risposta come testo e restituisci la 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 resultMemorizza il minimo accanto a ogni valore
Intuizione
Finché un valore si trova all’altezza i della pila, i valori sotto di esso non possono cambiare, quindi il più piccolo dei primi i valori resta fisso finché quel valore rimane lì. Memorizza quel numero accanto a ogni valore: una seconda pila mins in cui mins[i] è il più piccolo tra values[0..i].
Con un push, la nuova voce di mins è il minore tra x e la voce sottostante. Con un pop, rimuovi la cima di entrambe le pile; la cima di mins è di nuovo il minimo di ciò che rimane. getMin legge la cima di mins.
Nel primo esempio, i push 4, 1 e 7 memorizzano i minimi 4, 1 e 1. Rimuovere 7 lascia 1 in cima a mins, e rimuovere 1 lascia 4. Ogni operazione agisce solo sulle cime delle due pile, quindi ciascuna richiede O(1). Il costo è memorizzare un secondo numero per ogni valore.
Algoritmo
- Mantieni due stack della stessa altezza,
valuesemins. - Per
push x, inseriscixinvaluese inserisci inminsil minore traxe l'elemento in cima amins(xstesso seminsè vuoto). - Per
pop, rimuovi un elemento da entrambi gli stack. - Per
top, leggi l'elemento in cima avalues; pergetMin, leggi l'elemento in cima amins. - Registra ogni risposta come testo e restituisci l'elenco.
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 resultUna pila di valori minimi che cresce solo quando si raggiunge un nuovo minimo
Intuizione
Nel secondo approccio, mins spesso ripete sé stesso: inserisci 1 e poi 7, 8 e 9, e mins contiene 1, 1, 1, 1. Una voce ripetuta non ti dice nulla di nuovo. Quindi registra un valore in mins solo quando diventa il minimo e rimuovilo quando quello stesso valore esce da values.
Con un push, aggiungi x a mins se mins è vuoto o se x è minore o uguale al suo elemento in cima. Con un pop, se il valore che esce da values è uguale all'elemento in cima a mins, rimuovi anche l'elemento in cima a mins. L'elemento in cima a mins è sempre il minimo attuale: ogni valore inserito dopo di esso è maggiore, oppure era minore o uguale, è stato registrato a sua volta ed è stato rimosso da allora.
Il confronto deve essere <=, non <. Nel secondo esempio, -2 viene inserito due volte. Con < viene registrata solo la prima copia, il primo pop la rimuove da mins e getMin restituisce 3 mentre sulla pila c'è ancora un -2. Con <=, ogni copia ha una propria voce.
Tutte e quattro le operazioni restano O(1). Quando i valori arrivano dal più grande al più piccolo, mins diventa alto quanto values; quando il minimo cambia di rado, rimane corto.
Algoritmo
- Mantieni uno stack
valuese uno stackmins. - Per
push x, inseriscixinvalues. Seminsè vuoto oxè minore o uguale al suo elemento in cima, inserisci anchexinmins. - Per
pop, rimuovi l'elemento in cima avalues. Se il valore rimosso è uguale all'elemento in cima amins, rimuovi anche l'elemento in cima amins. - Per
top, leggi l'elemento in cima avalues; pergetMin, leggi l'elemento in cima amins. - Registra ogni risposta come testo e restituisci la 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
Trappole e casi limite
Gli errori qui riguardano le copie del minimo e ciò che una pop rimuove.
- Registrare un nuovo minimo solo quando
xè strettamente minore. In questo caso manca una seconda copia del minimo inminse, rimuovendo la prima copia, si perde il minimo mentre la seconda è ancora nello stack. Il secondo esempio lo dimostra. - Mantenere il minimo in una sola variabile. Funziona con gli inserimenti, ma dopo che il minimo viene rimosso la variabile non è aggiornata e per trovare il successivo valore più piccolo è necessaria una scansione.
- Confrontare gli interi boxed per riferimento. In Java,
Integer == Integerverifica se entrambi sono lo stesso oggetto. Questo è vero per i valori da -128 a 127, che Java mette in cache, ma non per la maggior parte dei valori più grandi, quindi il controllo della pop non funziona solo con i valori grandi. Prima converti inint, come fa il codice Java. - Rimuovere da
minsa ogni pop nel terzo approccio. Si riduce solo quando il valore rimosso è in cima; nel secondo approccio i due stack avanzano sempre insieme. - Restituire un numero per
pop. In questo formatopoprestituisce"null", comepush.
Domande frequenti4
Come si ottiene il minimo di uno stack in tempo O(1)?
Registra il minimo al momento dell'inserimento. Una pila cambia solo in cima, quindi il minimo dei valori al di sotto di qualsiasi altezza non può cambiare mentre quell'altezza è occupata. Mantieni una seconda pila con il minimo a ogni altezza, oppure solo con ogni nuovo minimo, e getMin diventa una lettura della sua cima.
Perché inserire nello stack dei minimi quando il valore è uguale al minimo attuale?
Perché il minimo può trovarsi più di una volta nello stack. Se registri solo i valori strettamente minori, due copie di -2 condividono una voce in mins. La prima rimozione di -2 elimina quella voce e getMin restituisce quindi il vecchio minimo, anche se la seconda copia di -2 è ancora presente. Registrare i valori uguali assegna a ogni copia una propria voce.
È possibile realizzare Min Stack con spazio aggiuntivo O(1)?
Sì, con uno stack e una variabile min. Quando inserisci uno x al di sotto del minimo corrente, memorizza invece 2x - min e imposta min = x; il numero memorizzato è quindi più piccolo di min, e questo lo contrassegna. Quando viene estratto un numero contrassegnato, il minimo precedente è 2 * min - stored. L’aritmetica va in overflow con gli interi a 32 bit vicino ai limiti, quindi servono valori a 64 bit, e la logica dei segni è soggetta a errori; la maggior parte degli intervistatori preferisce la versione con due stack.
Qual è la complessità temporale e spaziale di Min Stack?
Ogni operazione è O(1): push, pop, top e getMin leggono o modificano ciascuno solo la cima di uno o due stack. Lo spazio è O(n) per n valori memorizzati. Memorizzare il minimo accanto a ogni valore usa sempre 2n posizioni; memorizzare solo i nuovi minimi ne usa tra n + 1 e 2n.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def minStackOps(ops, args):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
Atteso
["null", "null", "null", "1", "null", "1", "null", "4"]