Next Greater Element I
Ti vengono forniti due array di interi distinti, nums1 e nums2, e ogni valore di nums1 compare anche in nums2. L’elemento successivo maggiore di un valore x è il primo valore alla destra di x in nums2 che è maggiore di x, oppure -1 se non esiste un valore del genere.
Restituisci un array contenente l’elemento successivo maggiore di ciascun valore di nums1, nell’ordine di nums1.
Funzione
- nums1integer-array
- i valori a cui rispondere, tutti presenti in nums2
- nums2integer-array
- l'array in cui guardi a destra di ciascun valore
- Restituisceinteger-array
- l'elemento successivo maggiore di ciascun valore di nums1, oppure -1, nell'ordine di nums1
Vincoli
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104- Tutti i valori in
nums1sono distinti e tutti i valori innums2sono distinti. - Ogni valore di
nums1è presente innums2.
Esempi
- Input
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Output
- [8, -1, 6]
- Spiegazione
- Dopo il 3 in
nums2vengono 8 e 2, e 8 è il primo maggiore di 3. Dopo 8 c’è solo 2, quindi a 8 viene assegnato -1. Il valore subito dopo 1 è 6, che è già maggiore.
- Input
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Output
- [-1, 9]
- Spiegazione
- Solo 4 segue 5, e 4 è più piccolo, quindi 5 riceve -1. Il valore subito dopo 2 è 9. Le risposte seguono l'ordine di
nums1, non l'ordine dinums2.
- Input
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Output
- [11, 10]
- Spiegazione
- Il primo valore dopo 10 è 11. Il primo valore dopo 0 è 10, che è più grande, quindi 0 riceve 10 anche se 11 viene dopo ed è ancora più grande.
+14 test nascosti all’invio
Per approfondire
Per ogni posizione di nums2, riesci a restituire quanti passi a destra si trova il suo prossimo elemento maggiore, con la stessa singola scansione?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
La scansione a destra di ciascun valore di
nums1può costare fino a 10^4 passaggi per valore. Le risposte dipendono solo danums2. Riesci a determinare l'elemento successivo maggiore di ogni valore dinums2in un'unica passata e poi cercare i valori dinums1?Scorri
nums2da sinistra a destra e conserva i valori che non hanno ancora incontrato un valore maggiore. Quando arriva un nuovo valore, è la risposta per ogni valore in attesa più piccolo di esso. I valori in attesa formano sempre una sequenza decrescente, quindi quelli più piccoli si trovano in cima a una pila.Per ogni valore di
nums2: finché il valore in cima allo stack è più piccolo, estrailo e registra il valore corrente come risposta in una mappa hash. Poi inserisci il valore corrente. Alla fine, rispondi a ogni valore dinums1consultando la mappa, con -1 per un valore che non è mai stato estratto.
Soluzione
Per un solo valore, la risposta è una scansione verso destra, ma una scansione per ogni valore di nums1 richiede fino a nums1.length × nums2.length passaggi. Le risposte dipendono solo da nums2, quindi puoi trovare contemporaneamente l'elemento successivo maggiore per ogni valore di nums2 usando una pila monotona, conservarli in una mappa hash e rispondere per nums1 tramite ricerca.
Trova ogni valore e scorri verso destra
Corretto, ma non termina sui test più grandi
Intuizione
Fai ciò che dice la definizione. Per un valore x di nums1, scorri nums2 finché non raggiungi x. Poi continua a scorrere e fermati al primo valore maggiore di x. Se arrivi alla fine senza trovarne uno, la risposta è -1.
È corretto perché la scansione visita in ordine i valori a destra di x, quindi il primo valore maggiore che incontra è il primo valore maggiore che c'è.
È lento quando le risposte sono lontane o mancano. Se nums2 è decrescente, nessuna scansione trova mai un valore maggiore e ogni valore di nums1 viene scandito fino alla fine. Con m valori in nums1 e n in nums2, si arriva fino a m × n passaggi: 10^8 quando entrambi gli array contengono 10^4 valori. Ogni scansione ripercorre anche tratti già percorsi dalle scansioni precedenti.
Algoritmo
- Scorri ogni valore
xdinums1. - Trova l’indice
jin cuinums2[j]è uguale ax. - Scorri
nums2a partire daj+1e fermati al primo valore maggiore dix. - Aggiungi quel valore oppure -1 se la scansione è arrivata alla fine.
- Restituisci le risposte raccolte.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return resultPila monotona e mappa hash
Intuizione
Ribalta la domanda. Invece di chiederti, per ogni valore, cosa viene dopo, scorri nums2 una volta e lascia che ogni nuovo valore risponda ai valori precedenti che supera. Tieni su uno stack i valori che non hanno ancora una risposta. Quando arriva un valore, rimuovi dalla cima tutti i valori più piccoli: il nuovo valore è il primo più grande alla loro destra, quindi è la loro risposta. Poi inserisci il nuovo valore, che è ancora in attesa della propria risposta.
Scorri nums2 = [1, 6, 3, 8, 2]. Inserisci 1. Poi arriva 6 e supera 1, quindi 1 corrisponde a 6; inserisci 6. Poi arriva 3, che non supera 6, e viene inserito in cima: lo stack è [6, 3]. Poi 8 rimuove 3 e 6, quindi entrambi corrispondono a 8; inserisci 8. Poi viene inserito 2. Lo stack termina con [8, 2] e quei due valori non hanno una risposta. Per nums1 = [3, 8, 1], la mappa restituisce [8, -1, 6].
Lo stack è sempre decrescente dal basso verso l’alto, perché un valore viene inserito solo dopo che tutti i valori più piccoli che lo sovrastano sono stati rimossi. Ecco perché devi guardare solo la cima. Un valore lascia lo stack nel momento in cui compare il primo valore più grande, quindi la risposta che registri è il primo, non il più grande.
Ogni valore di nums2 viene inserito una volta e rimosso al massimo una volta, quindi il ciclo interno esegue al massimo n rimozioni in totale durante l’intera scansione. Con le m ricerche, il tempo è O(n + m). La mappa collega i due array: i valori sono distinti, quindi un valore è una chiave sicura, anche se si trova in posizioni diverse in nums1 e nums2. Le soluzioni in C e R usano come mappa un array di 10^4+1 posizioni indicizzate per valore; questo funziona perché nessun valore supera 10^4.
Algoritmo
- Crea una mappa vuota e una pila vuota.
- Per ogni valore di
nums2, rimuovi dalla cima della pila tutti i valori più piccoli e associali al valore corrente. - Aggiungi il valore corrente alla pila.
- Per ogni valore di
nums1, restituisci la risposta associata oppure -1 se non ne ha una.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
Trappole e casi limite
Lo stack stesso richiede poco codice; gli errori riguardano cosa registri e dove guardi.
- Registrare il valore più grande a destra invece del primo valore più grande. In
nums2 = [3, 5, 1, 2, 4, 9, 0]la risposta per 1 è 2, non 9. - Restituire le risposte nell'ordine di
nums2, oppure una risposta per ogni valore dinums2. Il risultato contiene una voce per ogni valore dinums1, nel suo ordine. - Restituire un indice invece di un valore. Il problema chiede il valore più grande stesso.
- Leggere
nums2all'indice che un valore ha innums1. Lo stesso valore si trova in posizioni diverse nei due array; cercalo in base al valore, a questo serve la mappa. - Dimenticare i valori rimasti nello stack alla fine. Non hanno mai incontrato un valore più grande, quindi la loro risposta è -1; una ricerca nella mappa senza un valore predefinito non funziona o non restituisce nulla per loro.
- Guardare a sinistra o ricominciare dall'inizio di
nums2. Contano solo i valori a destra e l'array non ricomincia da capo.
Domande frequenti4
Qual è la complessità temporale di Next Greater Element I?
La soluzione con stack monotono richiede un tempo O(n + m), dove n è la lunghezza di nums2 e m quella di nums1. Ogni valore di nums2 viene inserito e rimosso dallo stack al massimo una volta, mentre per ogni valore di nums1 viene effettuata una ricerca nella mappa. La mappa e lo stack occupano uno spazio O(n). La scansione verso destra a partire da ogni valore richiede un tempo O(n·m).
Che cos'è uno stack monotono?
È uno stack i cui valori restano ordinati dal basso verso l’alto, qui in ordine decrescente. Prima di inserire un nuovo valore, rimuovi tutti quelli che comprometterebbero l’ordine: è in queste rimozioni che avviene il lavoro, perché ogni valore rimosso ha trovato il primo valore più grande alla sua destra. Risolve problemi come il prossimo valore maggiore, il prossimo valore minore e altri simili in tempo lineare.
Perché Next Greater Element I ha bisogno di una tabella hash?
La scansione dello stack produce le risposte nell'ordine in cui i valori escono dallo stack, associate ai valori di nums2. L'output deve seguire l'ordine di nums1, in cui gli stessi valori si trovano in altre posizioni. Poiché tutti i valori sono distinti, una mappa dal valore alla risposta collega i due array con una ricerca a tempo costante per valore.
Che cosa cambia se nums2 è circolare?
La ricerca di un valore più grande può quindi continuare dall'inizio dell'array. Esegui la stessa scansione dello stack sull'array due volte, usando l'indice i % n per i da 0 a 2n-1, e inserisci i valori nello stack solo durante il primo giro. I valori che rimangono nello stack dopo entrambi i giri non hanno alcun valore più grande, quindi la loro risposta è -1.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def nextGreaterElement(nums1, nums2):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Atteso
[8, -1, 6]