Cammina da sinistra a destra, usando una pila per tenere traccia del colore su cui ti trovi. Invece di una mappa discreta, utilizza i 10 numeri nel set di dati come punti di interruzione.
Iniziando con uno stack vuoto e impostando start
su 0, esegui il loop fino a raggiungere la fine:
- Se lo stack è vuoto:
- Cerca il primo colore a partire da o prima di
start
, e spingilo nello stack con tutti i colori di livello inferiore. Nell'elenco appiattito, segna l'inizio di quel colore.
- else (Se non vuoto):
- Trova il prossimo punto di inizio per qualsiasi colore con classificazione più alta in corrispondenza di o dopo
start
e trova la fine del colore corrente
- Se il colore successivo inizia per primo, spingerlo e tutto il resto sulla strada verso lo stack. Aggiorna la fine del colore corrente come inizio di questa e aggiungi l'inizio di questo colore alla lista appiattita.
- Se non ce ne sono e il colore corrente finisce per primo, imposta
start
alla fine di questo colore, espellilo dalla pila e controlla il colore con il livello più alto successivo
- Se
start
si trova nell'intervallo del colore successivo, aggiungi questo colore alla lista appiattita, a partire da start
.
- Se la pila si svuota, continua semplicemente il ciclo (torna al primo punto elenco).
Questo è un run-through mentale dati i tuoi dati di esempio:
# Initial data.
flattened = []
stack = []
start = 0
# Stack is empty. Look for the next starting point at 0 or later: "b", 0 - Push it and all lower levels onto stack
flattened = [ (b, 0, ?) ]
stack = [ r, b ]
start = 0
# End of "b" is 5.4, next higher-colored start is "g" at 2 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, ?) ]
stack = [ r, b, g ]
start = 2
# End of "g" is 12, next higher-colored start is "y" at 3.5 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, ?) ]
stack = [ r, b, g, y ]
start = 3.5
# End of "y" is 6.7, next higher-colored start is "o" at 6.7 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, ?) ]
stack = [ r, b, g, y, o ]
start = 6.7
# End of "o" is 10, and there is nothing starting at 12 or later in a higher color. Next off stack, "y", has already ended. Next off stack, "g", has not ended. Delimit and continue.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, ?) ]
stack = [ r, b, g ]
start = 10
# End of "g" is 12, there is nothing starting at 12 or later in a higher color. Next off stack, "b", is out of range (already ended). Next off stack, "r", is out of range (not started). Mark end of current color:
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12) ]
stack = []
start = 12
# Stack is empty. Look for the next starting point at 12 or later: "r", 12.5 - Push onto stack
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, ?) ]
stack = [ r ]
start = 12
# End of "r" is 13.8, and there is nothing starting at 12 or higher in a higher color. Mark end and pop off stack.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, 13.8) ]
stack = []
start = 13.8
# Stack is empty and nothing is past 13.8 - We're done.