Largest Rectangle in Histogram

Un rettangolo copre una sequenza di barre adiacenti da start a end e la sua altezza è limitata dalla barra più bassa della sequenza. Prova quindi ogni sequenza. Fissa start, poi aumenta end di una barra alla volta e tieni traccia dell’altezza minima incontrata fino a quel momento. Il rettangolo migliore su quella sequenza ha area lowest × (end-start+1).

In [2, 5, 6, 3, 4, 1], parti dal 5. Le sequenze danno 5 × 1 = 5, poi 5 × 2 = 10 con il 6, poi 3 × 3 = 9 quando si aggiunge il 3, 3 × 4 = 12 con il 4 e 1 × 5 = 5 con l’1. La risposta è 12. Aggiornare lowest man mano che la sequenza cresce mantiene ogni passaggio in O(1), quindi non devi mai ripassare la sequenza per trovare il suo minimo.

È corretto perché ogni rettangolo si trova sopra una qualche sequenza e, per una sequenza fissata, il rettangolo più alto che ci sta è alto esattamente quanto la barra più bassa. È lento perché ci sono n(n+1)/2 sequenze: circa 2 × 10^8 per 2 × 10^4 barre, e quel numero non dipende affatto dalle altezze. La maggior parte di queste sequenze viene interrotta da una barra bassa molto prima di raggiungere la fine, ma l’algoritmo esaustivo continua comunque ad ampliarle.

Inverti la ricerca. Nel rettangolo migliore, almeno una barra sottostante è esattamente alta quanto il rettangolo; altrimenti potresti alzare il rettangolo. Quindi la risposta è il massimo, considerando ogni barra i, tra i rettangoli alti esattamente heights[i] e larghi il più possibile. Si estendono finché incontrano una barra strettamente più bassa su ciascun lato. Chiama i loro indici left[i] e right[i], usando -1 e n quando non ce n'è nessuna. Il rettangolo copre le barre strettamente comprese tra loro: larghezza right[i]-left[i]-1. Si tratta di n candidati invece di n²/2.

Per trovare left[i] per ogni barra, procedi da sinistra a destra con uno stack di indici le cui altezze crescono rigorosamente dal basso verso l'alto. Quando arriva la barra i, rimuovi dallo stack tutti gli indici le cui barre sono alte almeno quanto heights[i]. Quelle barre non potranno mai essere la barra più vicina e più bassa né per i né per qualsiasi barra successiva, perché i è più vicina e non è più alta. Qualunque indice rimanga in cima è quello della barra più vicina e più bassa a sinistra. Poi inserisci i nello stack. La stessa scansione da destra a sinistra fornisce right[i].

Per [2, 5, 6, 3, 4, 1] le scansioni restituiscono left = [-1, 0, 1, 0, 3, -1] e right = [5, 3, 3, 5, 5, 6]. La barra di altezza 3 all'indice 3 è fermata dal 2 all'indice 0 e dall'1 all'indice 5, quindi il suo rettangolo è 3 × (5-0-1) = 12. Il 6 è stretto tra i suoi vicini e produce soltanto 6 × 1.

Ogni indice viene inserito una volta e rimosso al massimo una volta in ciascuna scansione, quindi entrambe le scansioni sono O(n), anche se una barra può rimuoverne molte. Il costo è costituito da due array aggiuntivi.

La scansione da sinistra a destra vede già ogni limite destro; lo scarta. Quando la barra i rimuove la barra t, heights[i] non è più alta di heights[t], quindi i è il punto in cui il rettangolo di t termina a destra. L’indice che resta sotto t nella pila è il punto in cui termina a sinistra. Quindi misura il rettangolo nel momento in cui rimuovi la barra: heights[t] × (i - below - 1), dove below è la nuova cima della pila, oppure -1 se la pila è vuota.

L’invariante: le altezze nella pila crescono strettamente dal basso verso l’alto, e l’indice sotto ciascun elemento è la barra più vicina alla sua sinistra che è più bassa. Ogni barra compresa tra le due è stata rimossa durante il processo, dalla barra stessa oppure da una barra che l’elemento ha rimosso in seguito, quindi nessuna di esse è più bassa dell’elemento. Le barre che non vengono mai rimosse arrivano fino alla fine, quindi dopo l’ultima barra elabori un’altra barra di altezza 0. È più bassa di tutte e svuota la pila.

Seguiamo [2, 5, 6, 3, 4, 1]. Inserisci 2, 5 e 6: la pila contiene gli indici [0, 1, 2]. Il 3 all’indice 3 rimuove il 6 (area 6 × (3-1-1) = 6) e il 5 (area 5 × (3-0-1) = 10), poi si ferma al 2 e viene inserito. Inserisci il 4. L’1 all’indice 5 rimuove il 4 (area 4), poi il 3, il cui rettangolo va dall’indice 1 all’indice 4: 3 × (5-0-1) = 12. Rimuove anche il 2 (2 × 5 = 10; la pila è vuota, quindi la larghezza è 5). Lo 0 conclusivo rimuove l’1 (1 × 6 = 6). Il massimo è 12.

Rimuovere con >= significa che una barra di uguale altezza può fermare una barra prima del previsto. È sicuro: la barra di uguale altezza prende il suo posto nella pila, eredita lo stesso limite sinistro e, quando viene rimossa in seguito, il suo rettangolo copre l’intera sequenza. In [3, 3, 3, 3] i primi tre 3 registrano larghezze 1, 2 e 3, e l’ultimo viene rimosso dallo 0 conclusivo con larghezza 4, ottenendo 12.