Padrão da Pilha Monotônica
Aplique a pilha monotônica para resolver daily-temperatures, largest-rectangle-in-histogram e next-greater-element em O(n).
Padrão da Pilha Monotônica é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é uma pilha monotônica?
Uma pilha monotônica é uma pilha que mantém uma invariante ordenada entre seus elementos. Uma pilha monotônica crescente tem elementos em ordem crescente da base ao topo; uma pilha monotônica decrescente tem elementos em ordem decrescente da base ao topo. Quando um novo elemento viola a invariante, os elementos são removidos até que ela seja restaurada e, então, o novo elemento é inserido.
Esse mecanismo simples permite responder em O(n) a consultas sobre o «elemento maior mais próximo» e o «elemento menor mais próximo», que exigiriam ingenuamente laços aninhados em O(n²).
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Próximo elemento maior (LeetCode 496)
Para cada elemento, encontre o primeiro elemento à sua direita que seja estritamente maior. Uma solução de força bruta em O(n²) percorre a sequência para a direita a partir de cada posição. A abordagem com pilha monotônica mantém uma pilha decrescente de índices. Quando um elemento maior é encontrado, remova todos os índices de elementos menores — o «próximo elemento maior» deles é o elemento atual. Os índices restantes não têm um próximo elemento maior (a resposta é -1).
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Próximo elemento maior em uma matriz circular
LeetCode 503 «Próximo Elemento Maior II»: o mesmo problema, mas a matriz é tratada como circular. Depois de chegar ao fim, volte ao início e verifique novamente. O truque é percorrer a matriz duas vezes (índices de 0 a 2n-1) e usar i % n para indexar a matriz original. Insira índices apenas no intervalo [0, n-1] para evitar o processamento duplicado.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Temperaturas diárias: solução completa
Revisão do LeetCode 739: para cada dia, quantos dias faltam até uma temperatura mais quente? A pilha monotônica mantém índices de dias com temperaturas em ordem decrescente. Quando um dia mais quente i é encontrado, remova da pilha todos os índices j de dias mais frios e registre result[j] = i - j. Os dias que permanecem na pilha nunca encontraram um dia mais quente, portanto seu resultado continua sendo 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Elemento menor anterior
A consulta sobre o «elemento menor anterior» pergunta: para cada elemento, qual é o valor menor mais próximo à sua esquerda? Use uma pilha monotônica crescente, processando os elementos da esquerda para a direita. Antes de inserir o índice i, o topo da pilha é o elemento menor anterior, pois todos os elementos maiores que o valor na posição i já foram removidos durante inserções anteriores, quando elementos maiores os fizeram sair da pilha.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Maior retângulo em um histograma
LeetCode 84 «Maior Retângulo em um Histograma»: uma pilha monotônica crescente de índices. Para cada barra, remova todas as barras mais altas que a atual. Para cada barra removida h, seu limite direito é o índice atual i, e seu limite esquerdo é o novo topo da pilha + 1 (ou 0 se a pilha estiver vazia). Área = h × (direita - esquerda). Acrescente uma sentinela de altura 0 para forçar a remoção de todas as barras restantes ao final.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Retângulo máximo (LeetCode 85)
LeetCode 85 «Retângulo Máximo» amplia o problema do histograma para uma matriz binária bidimensional. Para cada linha, calcule as alturas acumuladas das barras: se matrix[row][col] == '1', a altura é o número de 1 consecutivos acima e incluindo esta célula. Em seguida, aplique o algoritmo do «maior retângulo em um histograma» à matriz de alturas de cada linha. Tempo: O(m × n) para uma matriz m×n.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Armazenamento de água da chuva: abordagem com pilha
LeetCode 42 «Armazenamento de Água da Chuva» com uma pilha: mantenha uma pilha decrescente de índices. Quando uma barra mais alta é encontrada, forma-se um vale. Remova a base do vale; calcule a largura da água como (current_index - stack_top - 1) e a altura como (min(current_bar, new_stack_top_bar) - valley_height). Some todas as contribuições. Tempo: O(n), espaço: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Reconhecendo problemas de pilha monotônica
Sinais de que uma pilha monotônica é a ferramenta certa: o problema pede o elemento maior ou menor seguinte ou anterior, a resposta para cada elemento depende de elementos em uma direção específica ou uma solução ingênua em O(n²) envolve percorrer a sequência para a esquerda ou para a direita para cada elemento. A pilha armazena candidatos que podem ser respostas para elementos futuros e os descarta assim que surge um candidato melhor.
Decida sempre de antemão: crescente (para o elemento menor seguinte ou anterior) ou decrescente (para o elemento maior seguinte ou anterior) e em qual direção você fará o processamento.
Análise amortizada em O(n)
À primeira vista, os algoritmos de pilha monotônica parecem ser O(n log n) ou O(n²) por causa do laço interno ao laço de repetição. Porém, cada elemento é inserido na pilha no máximo uma vez e removido no máximo uma vez. O número total de operações de push é n, e o número total de operações de pop também é no máximo n. Portanto, em todas as iterações, o trabalho total é de 2n operações — O(n) amortizado, não O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nResumo: escolhas da invariante da pilha monotônica
Escolha a direção da pilha com base na consulta. Para o próximo elemento maior, use uma pilha decrescente — remova elementos quando o atual for maior. Para o próximo elemento menor, use uma pilha crescente — remova elementos quando o atual for menor. Para o maior retângulo, use uma pilha crescente e remova elementos quando surgir uma barra mais baixa. Para o máximo em uma janela deslizante, use uma fila de duas pontas decrescente e remova elementos pelas duas extremidades.
Escrever a invariante em um comentário antes de programar esclarece a lógica e acelera a depuração.
Verificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: uma pilha monotônica mantém uma invariante ordenada removendo os elementos que a violam antes de inserir o novo elemento, pilhas decrescentes respondem a consultas sobre o próximo elemento maior; pilhas crescentes respondem a consultas sobre o próximo elemento menor e o tempo total é O(n) amortizado, pois cada elemento é inserido e removido no máximo uma vez. A seguir, implementaremos filas usando pilhas e pilhas usando filas.
Perguntas Frequentes
A aula “Padrão da Pilha Monotônica” é grátis?
Sim — o texto completo de “Padrão da Pilha Monotônica” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Padrão da Pilha Monotônica”?
Aplique a pilha monotônica para resolver daily-temperatures, largest-rectangle-in-histogram e next-greater-element em O(n). Você pratica Coding 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding 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 3 de 4.
Quanto tempo leva a aula “Padrão da Pilha Monotônica”?
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 Coding Interview Prep?
Sim. Cada aula de Coding 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
- Implementação e Aplicações de Pilhas
- Implementação de Filas e Deque
- Padrão da Pilha Monotônica
- Simulação Mútua de Pilha e Fila