Largest Rectangle in Histogram

Um retângulo cobre uma sequência de barras vizinhas de start a end, e sua altura é limitada pela barra mais baixa da sequência. Então, experimente todas as sequências. Fixe start, depois aumente end uma barra por vez e mantenha a menor altura encontrada até então. A melhor área de retângulo nessa sequência é lowest × (end-start+1).

Em [2, 5, 6, 3, 4, 1], comece no 5. As sequências dão 5 × 1 = 5, depois 5 × 2 = 10 com o 6, depois 3 × 3 = 9 quando o 3 se junta, 3 × 4 = 12 com o 4 e 1 × 5 = 5 com o 1. A resposta é 12. Atualizar lowest à medida que a sequência cresce mantém cada etapa em O(1), então você nunca precisa percorrer novamente uma sequência para encontrar seu mínimo.

Isso está correto porque todo retângulo fica sobre alguma sequência e, para uma sequência fixa, o retângulo mais alto que cabe tem exatamente a altura da barra mais baixa. É lento porque há n(n+1)/2 sequências: cerca de 2 × 10^8 para 2 × 10^4 barras, e essa quantidade não depende das alturas. A maioria dessas sequências é interrompida por uma barra baixa muito antes de chegar ao fim, mas a força bruta continua estendendo-as mesmo assim.

Inverta a busca. No melhor retângulo, pelo menos uma barra sob ele tem exatamente a mesma altura do retângulo; caso contrário, você poderia aumentá-lo. Portanto, a resposta é o melhor, entre todas as barras i, de um retângulo com exatamente heights[i] de altura que se estende o máximo possível. Ele se estende até encontrar uma barra estritamente mais baixa de cada lado. Chame seus índices de left[i] e right[i], usando -1 e n quando não houver nenhuma. O retângulo cobre as barras estritamente entre elas: largura right[i]-left[i]-1. São n candidatos, em vez de n²/2.

Para encontrar left[i] para cada barra, percorra da esquerda para a direita com uma pilha de índices cujas alturas aumentam estritamente da base ao topo. Quando a barra i chega, remova todos os índices cujas barras são pelo menos tão altas quanto heights[i]. Essas barras nunca poderão ser a barra mais próxima e mais baixa para i nem para qualquer barra depois dela, porque i está mais perto e não é mais alta. O que restar no topo será a barra mais próxima e mais baixa à esquerda. Em seguida, empilhe i. A mesma passagem da direita para a esquerda fornece right[i].

Para [2, 5, 6, 3, 4, 1], as passagens fornecem left = [-1, 0, 1, 0, 3, -1] e right = [5, 3, 3, 5, 5, 6]. A barra de altura 3 no índice 3 é limitada pelo 2 no índice 0 e pelo 1 no índice 5, então seu retângulo mede 3 × (5-0-1) = 12. O 6 fica limitado pelos vizinhos e só resulta em 6 × 1.

Cada índice é empilhado uma vez e removido no máximo uma vez em cada passagem, portanto ambas as passagens são O(n), mesmo que uma barra possa remover muitas. O custo são dois arrays extras.

A passagem da esquerda para a direita já encontra cada limite à direita; ela o descarta. Quando a barra i remove a barra t da pilha, heights[i] não é maior que heights[t], então i é onde o retângulo de t termina à direita. E o índice que fica sob t na pilha é onde ele termina à esquerda. Portanto, meça o retângulo no momento em que remover a barra: heights[t] × (i - below - 1), em que below é o novo topo da pilha, ou -1 se a pilha agora estiver vazia.

O invariante: as alturas na pilha aumentam estritamente da base ao topo, e o índice abaixo de cada entrada é a barra mais próxima à sua esquerda que é mais baixa do que ela. Todas as barras entre as duas foram removidas no caminho, seja pela própria entrada, seja por uma barra que a entrada removeu depois; portanto, nenhuma delas é mais baixa do que a entrada. As barras que nunca são removidas chegam até o fim, então, depois de processar a última barra, processe mais uma barra de altura 0. Ela é mais baixa do que todas e esvazia a pilha.

Percorra [2, 5, 6, 3, 4, 1]. Empilhe 2, 5 e 6: a pilha contém os índices [0, 1, 2]. O 3 no índice 3 remove o 6 (área 6 × (3-1-1) = 6) e o 5 (área 5 × (3-0-1) = 10), depois para no 2 e é empilhado. Empilhe o 4. O 1 no índice 5 remove o 4 (área 4), depois o 3, cujo retângulo vai do índice 1 ao 4: 3 × (5-0-1) = 12. Ele também remove o 2 (2 × 5 = 10; a pilha está vazia, então a largura é 5). O 0 de fechamento remove o 1 (1 × 6 = 6). O maior valor é 12.

Remover com >= significa que uma barra de mesma altura pode fazer uma barra parar antes. Isso é seguro: a barra de mesma altura ocupa o lugar dela na pilha, herda o mesmo limite à esquerda e, quando for removida depois, seu retângulo cobrirá toda a sequência. Em [3, 3, 3, 3], os três primeiros 3 registram larguras 1, 2 e 3, e o último é removido pelo 0 de fechamento com largura 4, resultando em 12.