DSA Interview Prep · Aula

Maior retângulo no histograma

Use uma pilha monotônica para acompanhar os limites esquerdos e calcular, em uma única passagem, o retângulo de maior área que cabe em um histograma.

Maior retângulo no histograma é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.

Problema: Maior Retângulo em um Histograma

O problema do Maior Retângulo em um Histograma (LeetCode 84) fornece um vetor de inteiros não negativos que representa as alturas das barras de um histograma, em que cada barra tem largura 1. Encontre a área do maior retângulo que pode ser formado dentro do histograma. O retângulo deve abranger barras contíguas, e sua altura é limitada pela barra mais baixa que ele cobre.

Uma abordagem de força bruta: para cada par (i, j), calcule a altura mínima em [i, j] e multiplique por (j - i + 1). Isso resulta em O(n³), ou em O(n²) com os valores mínimos pré-calculados — lento demais. A solução com pilha monotônica é executada em O(n).

# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')

# Brute force for small inputs:
def brute_force(heights):
    n = len(heights)
    max_area = 0
    for i in range(n):
        min_h = heights[i]
        for j in range(i, n):
            min_h = min(min_h, heights[j])
            max_area = max(max_area, min_h * (j - i + 1))
    return max_area

print('Brute force answer:', brute_force(heights))  # 10

Ideia Principal: O Que Limita o Retângulo de Cada Barra?

Para cada barra i com altura h, o maior retângulo em que ela pode ser o mínimo se estende para a esquerda até a primeira barra mais baixa que h e para a direita até a primeira barra mais baixa que h. A largura é right_boundary - left_boundary - 1 e a área é h × width.

Isso reformula o problema: para cada barra, encontre seu elemento menor anterior (PSE) e seu elemento menor seguinte (NSE). É exatamente isso que uma pilha monotônica crescente calcula. No momento em que fazemos pop da barra i (porque uma barra mais baixa foi encontrada), a barra atual é seu NSE, e o topo da pilha depois do pop é seu PSE.

heights = [2, 1, 5, 6, 2, 3]
n = len(heights)

# Find PSE and NSE for each bar
pse = [-1] * n   # index of previous smaller element
nse = [n] * n    # index of next smaller element (default: beyond array)

# PSE
stack = []
for i in range(n):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    pse[i] = stack[-1] if stack else -1
    stack.append(i)

# NSE
stack = []
for i in range(n - 1, -1, -1):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    nse[i] = stack[-1] if stack else n
    stack.append(i)

max_area = 0
for i in range(n):
    width = nse[i] - pse[i] - 1
    area = heights[i] * width
    print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
    max_area = max(max_area, area)
print('Max area:', max_area)

Solução em Uma Passagem com Pilha Monotônica

A abordagem de duas passagens acima funciona, mas pode ser combinada em uma única passagem. Processe as barras da esquerda para a direita com uma pilha monotônica crescente. Quando a barra i for mais baixa que o topo da pilha, faça pop do topo — a altura da barra removida é a altura de um retângulo, seu limite direito é i e seu limite esquerdo é o novo topo da pilha + 1.

Um truque comum: use append para acrescentar uma sentinela 0 ao final de heights. Isso garante que todas as barras sejam removidas da pilha ao final, mesmo que nenhuma barra mais baixa apareça naturalmente. Sem a sentinela, é necessário fazer uma etapa de limpeza após o laço para os elementos restantes da pilha.

def largest_rectangle(heights):
    stack = []   # monotonic increasing: indices of bars
    max_area = 0
    heights = heights + [0]  # sentinel: forces all bars to be popped

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]       # height of the rectangle
            width = i if not stack else i - stack[-1] - 1  # left boundary
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

print(largest_rectangle([2, 1, 5, 6, 2, 3]))  # 10
print(largest_rectangle([2, 4]))               # 4
print(largest_rectangle([1, 1]))               # 2
print(largest_rectangle([0, 9]))               # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3]))  # 16

Rastreamento do Algoritmo de Uma Passagem

Vamos rastrear [2, 1, 5, 6, 2, 3, 0] (com sentinela) passo a passo:

i=0, h=2: insira 0. Pilha: [0]
i=1, h=1: pop 0 (h=2, largura=1, área=2). Pilha vazia, insira 1. Pilha: [1]
i=2, h=5: 5>1, insira 2. Pilha: [1,2]
i=3, h=6: 6>5, insira 3. Pilha: [1,2,3]
i=4, h=2: pop 3 (h=6,largura=4-2-1=1,área=6), pop 2 (h=5,largura=4-1-1=2,área=10★), 2>1, pare. Insira 4. Pilha: [1,4]
i=5, h=3: 3>2, insira 5. Pilha: [1,4,5]
i=6, sentinela h=0: faça pop de todos, calculando as áreas...

def largest_rectangle_trace(heights):
    stack = []
    max_area = 0
    hs = heights + [0]

    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] > h:
            top = stack.pop()
            w = i if not stack else i - stack[-1] - 1
            area = hs[top] * w
            print(f'  Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
            if area > max_area:
                max_area = area
                print(' *** NEW MAX ***', end='')
            print()
        print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
        stack.append(i)
    print(f'Max area: {max_area}')
    return max_area

largest_rectangle_trace([2, 1, 5, 6, 2, 3])

Cálculo da Largura: Por Que i - pilha[-1] - 1?

Quando removemos a barra j da pilha, sabemos que: o limite direito do retângulo de j é i (a primeira barra à direita mais baixa que j). O limite esquerdo é a barra imediatamente abaixo de j na pilha após a remoção — vamos chamá-la de k. Portanto, a largura é i - k - 1 (as barras de k+1 a i-1, inclusive).

Se a pilha estiver vazia após a remoção, o retângulo de j se estenderá até a extremidade esquerda (índice 0). A largura será simplesmente i (os índices de 0 a i-1, todos com altura pelo menos igual a heights[j]). Este é o caso especial width = i if not stack else i - stack[-1] - 1.

# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
#   stack after pop = [0, 1]   => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
#   stack after pop = [0]       => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.

def compute_boundaries(heights):
    hs = heights + [0]
    stack = []
    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] > h:
            top = stack.pop()
            if stack:
                left = stack[-1] + 1
                width = i - stack[-1] - 1
            else:
                left = 0
                width = i
            print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
        stack.append(i)

compute_boundaries([2, 1, 5, 6, 2, 3])

Retângulo Máximo em uma Matriz Binária

Retângulo Máximo (LeetCode 85) estende o problema do histograma para uma matriz binária bidimensional. Para cada linha, calcule a altura de 1s consecutivos acima de cada célula. Isso cria um histograma para essa linha. Aplique o algoritmo do maior retângulo em um histograma ao histograma de cada linha. O máximo geral entre todas as linhas é a resposta.

Isso reduz um problema bidimensional a n problemas unidimensionais repetidos de histogramas. A complexidade de tempo é O(m × n) para uma matriz com m linhas e n colunas — uma passagem pelo histograma para cada linha, com cada passagem levando O(n).

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    n = len(matrix[0])
    heights = [0] * n
    max_area = 0

    def hist_max_area(h):
        stack, area = [], 0
        for i, hh in enumerate(h + [0]):
            while stack and h[stack[-1]] > hh:
                top = stack.pop()
                w = i if not stack else i - stack[-1] - 1
                area = max(area, h[top] * w)
            stack.append(i)
        return area

    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        max_area = max(max_area, hist_max_area(heights[:]))
    return max_area

matrix = [['1','0','1','0','0'],
          ['1','0','1','1','1'],
          ['1','1','1','1','1'],
          ['1','0','0','1','0']]
print(maximal_rectangle(matrix))  # 6

Casos Limite em Problemas de Histogramas

Casos limite importantes a serem tratados:

Todas as alturas iguais: o vetor inteiro forma um único retângulo; resposta = n × altura
Ordem monotonicamente crescente: nenhum pop ocorre até a sentinela; a área da última barra é a maior
Uma única barra: resposta = altura[0]
Barras com altura 0: elas funcionam como sentinelas naturais, dividindo o histograma em segmentos independentes

A sentinela (acrescentar 0) ao final trata o caso de ordem monotonicamente crescente, forçando a remoção de todas as barras restantes ao final. Sem ela, é necessário um laço de limpeza separado após a iteração principal.

def largest_rectangle(heights):
    stack = []
    max_area = 0
    heights = heights + [0]
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, heights[top] * w)
        stack.append(i)
    return max_area

# Edge cases
print(largest_rectangle([5, 5, 5, 5]))    # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5]))              # 5 (single bar)
print(largest_rectangle([0, 0, 0]))        # 0 (all zero)
print(largest_rectangle([3, 0, 3]))        # 3 (zero splits)

Alternativa de Divisão e Conquista

O problema do histograma também pode ser resolvido com divisão e conquista: divida na barra de altura mínima, resolva cada metade recursivamente e compare com o retângulo que abrange toda a largura usando a altura mínima. Isso resulta em O(n log n) no caso médio, mas em O(n²) no pior caso para entradas ordenadas.

A abordagem com pilha monotônica é estritamente melhor, com O(n) no pior caso. No entanto, compreender a abordagem de divisão e conquista aprofunda a intuição sobre o problema e explica por que a barra de altura mínima em qualquer segmento é sempre o fator limitante dos retângulos de largura total.

def largest_rectangle_dc(heights, lo=0, hi=None):
    if hi is None:
        hi = len(heights) - 1
    if lo > hi:
        return 0
    # Find the index of the minimum height in [lo, hi]
    min_idx = lo
    for i in range(lo, hi + 1):
        if heights[i] < heights[min_idx]:
            min_idx = i
    # Three options:
    # 1. Max rect entirely in left half
    # 2. Max rect entirely in right half
    # 3. Max rect spanning entire [lo, hi] with height = min
    full_width_area = heights[min_idx] * (hi - lo + 1)
    left_area  = largest_rectangle_dc(heights, lo, min_idx - 1)
    right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
    return max(full_width_area, left_area, right_area)

print(largest_rectangle_dc([2, 1, 5, 6, 2, 3]))  # 10

Padrão de Histograma: Contagem de Subvetores

Um problema relacionado que utiliza a mesma técnica de pilha: conte o número de subvetores em um histograma cujo elemento mínimo seja igual a um determinado alvo. Isso é respondido calculando o PSE e o NSE de cada barra e, em seguida, utilizando a fórmula (i - pse[i]) × (nse[i] - i), que conta os sub-histogramas em que a barra i é o mínimo.

Essa técnica de “contagem à esquerda × contagem à direita” aparece em vários problemas do LeetCode: soma dos mínimos de subvetores (907), contagem de substrings com todos os caracteres únicos e problemas que utilizam a técnica de contribuição. A pilha monotônica calcula o PSE e o NSE em O(n), permitindo uma contribuição de O(1) por elemento.

def sum_of_subarray_minimums(arr):
    n = len(arr)
    pse = [-1] * n   # previous strictly smaller element
    nse = [n] * n    # next smaller or equal element

    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        pse[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        nse[i] = stack[-1] if stack else n
        stack.append(i)

    MOD = 10**9 + 7
    total = 0
    for i in range(n):
        left_count = i - pse[i]          # subarrays where i is leftmost min
        right_count = nse[i] - i        # subarrays where i is the min
        total += arr[i] * left_count * right_count
    return total % MOD

print(sum_of_subarray_minimums([3, 1, 2, 4]))  # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3]))  # 444

Dicas práticas para entrevistas

Quando encontrar um problema de histograma em uma entrevista, siga esta lista de verificação:

Esclareça: as alturas podem ser 0? Qual é o resultado — área, índices ou contagem?
Comece com a força bruta e informe a complexidade O(n²) ou O(n³)
Mencione que a contribuição de cada barra depende de sua extensão à esquerda e à direita até a barra mais próxima que seja mais baixa
Introduza PSE/NSE → pilha monotônica → solução O(n)
Trate o truque da sentinela (append 0) para simplificar o código
Trace um exemplo pequeno no quadro branco

Um acompanhamento comum é estender o problema para 2D (retângulo máximo). Demonstre que é possível reduzi-lo a n problemas de histograma, cada um com O(n), totalizando O(m×n).

# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):  # sentinel forces final pops
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

# Verify all test cases from earlier
test_cases = [
    ([2, 1, 5, 6, 2, 3], 10),
    ([6, 7, 5, 2, 4, 5, 9, 3], 16),
    ([1], 1),
    ([2, 0, 2], 2),
    ([], 0),
]
for heights, expected in test_cases:
    if not heights:
        result = 0
    else:
        result = largest_rectangle_in_histogram(heights)
    status = 'PASS' if result == expected else 'FAIL'
    print(f'{status}: {heights} => {result} (expected {expected})')

Soma dos intervalos de subvetores e variantes semelhantes

A técnica de PSE/NSE generaliza-se para vários problemas do LeetCode. Soma dos intervalos de subvetores (2104) pede a soma de (máximo - mínimo) em todos os subvetores. Isso equivale a (soma dos máximos dos subvetores) menos (soma dos mínimos dos subvetores), cada um calculado com uma pilha monotônica em O(n). Número de pessoas visíveis em uma fila (1944) usa uma pilha decrescente na qual cada pop contabiliza uma pessoa visível. Reconhecer essa família de problemas depende de perceber a frase 'para cada elemento, até onde ele pode dominar?' — a resposta é sempre PSE/NSE com uma pilha monotônica.

def sum_subarray_ranges(nums):
    n = len(nums)
    # Sum of subarray max - sum of subarray min
    def contrib(arr, is_max):
        # Count contribution of each element as max (or min)
        n = len(arr)
        left = [0]*n; right = [0]*n
        stack = []
        for i in range(n):
            while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
                stack.pop()
            left[i] = i - (stack[-1] if stack else -1)
            stack.append(i)
        stack = []
        for i in range(n-1, -1, -1):
            while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
                stack.pop()
            right[i] = (stack[-1] if stack else n) - i
            stack.append(i)
        return sum(arr[i] * left[i] * right[i] for i in range(n))
    return contrib(nums, True) - contrib(nums, False)

print(sum_subarray_ranges([1, 2, 3]))    # 4
print(sum_subarray_ranges([1, 3, 3]))    # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1]))  # 59

Verificação rápida

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.

Recapitulação da lição

Nesta lição, você aprendeu: para cada barra, o maior retângulo que ela contém tem limites definidos pela barra mais próxima e mais baixa de cada lado (PSE e NSE), uma pilha monotônica crescente calcula todos os limites PSE/NSE em uma única passagem O(n), encontrando ambos à medida que as barras são retiradas, e adicionar uma sentinela 0 garante que todas as barras sejam retiradas da pilha, simplificando o código para um único laço. Em seguida, aplicaremos a fila monotônica de duas extremidades para resolver o máximo em janela deslizante em O(n).

Perguntas Frequentes

A aula “Maior retângulo no histograma” é grátis?

Sim — o texto completo de “Maior retângulo no histograma” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.

O que vou aprender em “Maior retângulo no histograma”?

Use uma pilha monotônica para acompanhar os limites esquerdos e calcular, em uma única passagem, o retângulo de maior área que cabe em um histograma. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.

Quanto tempo leva a aula “Maior retângulo no histograma”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de DSA Interview Prep?

Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

Pilha monotônica: crescente vs decrescente
Maior retângulo no histograma
Máximo em janela deslizante com deque monotônica
Acúmulo de água da chuva: pilha e dois ponteiros

← Voltar para DSA Interview Prep