Largest Rectangle in Histogram

Prostokąt obejmuje ciąg sąsiadujących słupków od start do end, a jego wysokość jest ograniczona przez najniższy słupek w tym ciągu. Sprawdź więc każdy ciąg. Ustal start, a następnie wydłużaj ciąg, zwiększając end o jeden słupek i zapamiętując najniższą dotąd wysokość. Najlepszy prostokąt dla tego ciągu ma pole lowest × (end-start+1).

W ciągu [2, 5, 6, 3, 4, 1] zacznij od 5. Dla kolejnych ciągów otrzymujemy 5 × 1 = 5, następnie 5 × 2 = 10 po dodaniu 6, potem 3 × 3 = 9 po dołączeniu 3, 3 × 4 = 12 po dodaniu 4 i 1 × 5 = 5 po dodaniu 1. Odpowiedzią jest 12. Aktualizowanie lowest podczas wydłużania ciągu sprawia, że każdy krok zajmuje O(1), więc nie musisz ponownie przeszukiwać ciągu, by znaleźć jego minimum.

To rozwiązanie jest poprawne, ponieważ każdy prostokąt obejmuje jakiś ciąg, a dla ustalonego ciągu najwyższy pasujący prostokąt ma dokładnie wysokość najniższego słupka. Jest powolne, ponieważ istnieje n(n+1)/2 ciągów: około 2 × 10^8 dla 2 × 10^4 słupków, a ich liczba w ogóle nie zależy od wysokości. Większość tych ciągów zostaje ograniczona przez niski słupek na długo przed końcem, ale metoda brute force i tak nadal je wydłuża.

Odwróćmy sposób szukania. W najlepszym prostokącie co najmniej jeden słupek pod nim ma dokładnie taką samą wysokość jak prostokąt; w przeciwnym razie można by podnieść prostokąt. Odpowiedzią jest więc najlepszy spośród wszystkich słupków i prostokąt o wysokości dokładnie heights[i], rozciągnięty na maksymalną szerokość. Rozciąga się on do napotkania po każdej stronie słupka ściśle niższego. Nazwijmy ich indeksy left[i] i right[i], używając -1 i n, gdy nie ma takiego słupka. Prostokąt obejmuje słupki leżące ściśle między nimi: szerokość right[i]-left[i]-1. Daje to n kandydatów zamiast n²/2.

Aby znaleźć left[i] dla każdego słupka, przejdź od lewej do prawej, używając stosu indeksów, których wysokości rosną ściśle od dołu do góry. Gdy pojawi się słupek i, zdejmuj ze stosu każdy indeks, którego słupek jest co najmniej tak wysoki jak heights[i]. Te słupki nigdy nie mogą być najbliższymi niższymi słupkami dla i ani dla żadnego kolejnego słupka, ponieważ i jest bliżej i nie jest wyższy. To, co pozostanie na szczycie stosu, jest najbliższym niższym słupkiem po lewej. Następnie dodaj i na stos. Ten sam przebieg od prawej do lewej wyznacza right[i].

Dla [2, 5, 6, 3, 4, 1] przebiegi dają left = [-1, 0, 1, 0, 3, -1] i right = [5, 3, 3, 5, 5, 6]. Słupek o wysokości 3 na indeksie 3 jest ograniczony przez słupek o wysokości 2 na indeksie 0 i słupek o wysokości 1 na indeksie 5, więc jego prostokąt ma pole 3 × (5-0-1) = 12. Słupek o wysokości 6 jest ograniczony przez sąsiadów i daje tylko 6 × 1.

Każdy indeks jest dodawany na stos raz i zdejmowany z niego co najwyżej raz w każdym przebiegu, więc oba przebiegi mają złożoność O(n), mimo że jeden słupek może spowodować zdjęcie wielu elementów ze stosu. Kosztem są dwie dodatkowe tablice.

Przebieg od lewej do prawej już napotyka każdą prawą granicę; odrzuca ją. Gdy słupek i zdejmuje ze stosu słupek t, heights[i] nie jest większe niż heights[t], więc i to miejsce, w którym prostokąt słupka t kończy się z prawej strony. Indeks znajdujący się na stosie bezpośrednio pod t to miejsce, w którym kończy się z lewej strony. Zatem zmierz prostokąt w chwili zdejmowania słupka ze stosu: heights[t] × (i - below - 1), gdzie below to nowy szczyt stosu albo -1, jeśli stos jest teraz pusty.

Niezmiennik: wysokości na stosie rosną ściśle od dołu do góry, a indeks pod każdym wpisem wskazuje najbliższy słupek po jego lewej stronie, który jest od niego niższy. Każdy słupek między nimi został zdjęty ze stosu po drodze, albo przez ten wpis, albo przez słupek, który ten wpis zdjął później, więc żaden z nich nie jest niższy od tego wpisu. Słupki, które nigdy nie zostaną zdjęte ze stosu, sięgają aż do końca, więc po przetworzeniu ostatniego słupka przetwórz jeszcze jeden słupek o wysokości 0. Jest niższy od wszystkich i opróżnia stos.

Prześledźmy [2, 5, 6, 3, 4, 1]. Wstaw 2, 5 i 6: stos zawiera indeksy [0, 1, 2]. Wartość 3 na indeksie 3 zdejmuje ze stosu 6 (pole 6 × (3-1-1) = 6) i 5 (pole 5 × (3-0-1) = 10), po czym zatrzymuje się na 2 i zostaje dodana na stos. Dodaj 4. Wartość 1 na indeksie 5 zdejmuje ze stosu 4 (pole 4), a następnie 3, którego prostokąt rozciąga się od indeksu 1 do 4: 3 × (5-0-1) = 12. Zdejmuje też 2 ze stosu (2 × 5 = 10; stos jest pusty, więc szerokość wynosi 5). Końcowe 0 zdejmuje ze stosu 1 (1 × 6 = 6). Największe pole wynosi 12.

Zdejmowanie ze stosu przy warunku >= oznacza, że słupek o tej samej wysokości może przedwcześnie zatrzymać inny słupek. To bezpieczne: słupek o tej samej wysokości zajmuje jego miejsce na stosie, dziedziczy tę samą lewą granicę, a gdy zostanie później zdjęty ze stosu, jego prostokąt obejmie cały ciąg. Dla [3, 3, 3, 3] pierwsze trzy słupki o wysokości 3 wyznaczają szerokości 1, 2 i 3, a ostatni zostaje zdjęty ze stosu przez końcowe 0 przy szerokości 4, co daje 12.