Pilha monotônica: crescente vs decrescente
Mantenha uma pilha crescente ou decrescente para responder eficientemente a consultas sobre o próximo elemento maior e o elemento anterior menor em O(n).
Pilha monotônica: crescente vs decrescente é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 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 seus elementos em ordem, sempre crescente da base ao topo ou sempre decrescente. Antes de inserir um novo elemento, removemos com pop todos os elementos que violam the invariante monotônica. Essa estrutura restrita permite soluções O(n) para problemas que, de outra forma, exigiriam laços aninhados O(n²).
A ideia central: cada elemento é inserido e removido no máximo uma vez, portanto the número total de operações durante todo o percurso da matriz é O(n), e não O(n²). No momento em que removemos um elemento, encontramos a resposta que ele aguardava.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Primeiro Elemento Maior à Direita I
O problema do Próximo Elemento Maior: para cada elemento, encontre o primeiro elemento à sua direita que seja maior. Um laço duplo de força bruta O(n²) é lento demais. Com uma pilha monotônica decrescente, resolvemos isso em O(n).
Processe os elementos da esquerda para a direita. Antes de inserir o elemento i, remova com pop da pilha todos os elementos menores que nums[i] — nums[i] é o próximo elemento maior para todos eles. Após processar todos os elementos, quaisquer itens restantes na pilha não têm elemento maior à sua direita (resposta = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]Próximo Elemento Maior: Rastreamento do Algoritmo
Vamos rastrear [2, 1, 2, 4, 3] passo a passo. Mantemos uma pilha decrescente de índices cujo próximo elemento maior ainda não foi encontrado.
- i=0, valor=2: pilha vazia, insira 0. Pilha: [0]
- i=1, valor=1: 1 < nums[0]=2, insira 1. Pilha: [0,1]
- i=2, valor=2: pop 1 (nums[1]=1 < 2), resultado[1]=2; agora nums[0]=2 não é < 2, insira 2. Pilha: [0,2]
- i=3, valor=4: pop 2 (resultado[2]=4), pop 0 (resultado[0]=4), insira 3. Pilha: [3]
- i=4, valor=3: 3 < nums[3]=4, insira 4. Pilha: [3,4]
- Fim: os elementos 3 e 4 da pilha têm resultado=-1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Elemento Menor Anterior
As pilhas monotônicas também respondem a consultas de elemento menor anterior (PSE): para cada elemento, o elemento mais próximo à sua esquerda que seja menor. Em vez de fazer pop ao encontrar um elemento maior, fazemos pop ao encontrar um elemento maior ou igual e registramos o topo da pilha como o PSE antes de inserir o novo elemento.
A direção muda: continuamos processando da esquerda para a direita, mas, em vez de responder às perguntas enquanto fazemos pop, respondemos imediatamente antes de inserir. O topo da pilha nesse momento é o elemento menor mais próximo à esquerda. Se a pilha estiver vazia, não haverá elemento menor à esquerda (a resposta será -1 ou um valor sentinela).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Temperaturas Diárias: Esperando por Dias Mais Quentes
O problema de Temperaturas Diárias (LeetCode 739): dadas as temperaturas diárias, retorne um vetor em que cada elemento seja o número de dias até uma temperatura mais quente. Esse é exatamente o padrão do próximo elemento maior, mas, em vez do valor maior, queremos o número de dias (a diferença entre os índices).
Utilize uma pilha monotônica decrescente de índices. Quando encontramos uma temperatura mais quente no índice i, faça pop de todos os índices j da pilha para os quais temps[j] < temps[i] e defina result[j] = i - j. Os índices restantes não têm nenhum dia futuro mais quente (resultado = 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Pilha Crescente vs. Decrescente: Quando Usar Cada Uma
Escolher a direção correta da pilha é fundamental:
- Pilha monotônica decrescente (faça pop quando o atual > topo): responde a consultas sobre o próximo elemento maior e o elemento maior anterior. É utilizada nos problemas de temperaturas diárias, maior retângulo e água acumulada pela chuva.
- Pilha monotônica crescente (faça pop quando o atual < topo): responde a consultas sobre o próximo elemento menor e o elemento menor anterior. É utilizada para encontrar a amplitude dos preços das ações e o número de pessoas visíveis em uma fila.
Lembre-se: o elemento que causa um pop é a resposta à consulta do elemento removido — seja o próximo elemento maior ou o próximo elemento menor, dependendo de qual invariável é mantida.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Próximo Elemento Maior em um Vetor Circular
Próximo Elemento Maior II (LeetCode 503): dado um vetor circular (com retorno ao início), encontre o próximo elemento maior. O truque é processar o vetor duas vezes, duplicando os índices: percorra de 0 a 2n-1, utilizando index % n para retornar ao início. Insira na pilha apenas os índices de 0 a n-1 (na primeira passagem), para não contar os elementos duas vezes.
Como alternativa, processe o vetor na segunda passagem sem inserir novos índices — apenas fazendo pop. Isso trata corretamente a busca circular adiante sem duplicar o vetor de fato, mantendo o espaço O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Problema da Amplitude das Ações
O problema da Amplitude das Ações: dados os preços diários das ações, calcule a amplitude de cada dia — o número de dias consecutivos anteriores cujo preço seja menor ou igual ao preço de hoje. Esse é, disfarçado, o problema do elemento maior anterior: a amplitude é a distância entre hoje e o dia mais próximo com um preço estritamente maior.
Utilize uma pilha monotônica decrescente. Ao processar o dia i, faça pop de todos os dias cujo preço seja ≤ o atual. A amplitude é i - stack[-1] se a pilha não estiver vazia, ou i + 1 se estiver vazia (o preço é o maior até agora). Em seguida, insira i.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Pilha Monotônica para Pessoas Visíveis em uma Fila
O problema do Número de Pessoas Visíveis em uma Fila: as pessoas ficam em uma fila, cada uma com uma altura. A pessoa i consegue ver a pessoa j (j > i) se todas as pessoas entre elas forem mais baixas do que ambas. Esse problema utiliza uma pilha monotônica decrescente.
Processe da direita para a esquerda. Mantenha uma pilha decrescente de alturas. Para cada pessoa, conte quantas pessoas ela consegue ver: faça pop de todas as pessoas mais baixas (visíveis, mas bloqueadas depois), somando 1 se a pilha ainda não estiver vazia (a primeira pessoa mais alta também estará visível). Isso resulta em O(n) no total, pois cada pessoa é inserida e removida no máximo uma vez.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]Garantia O(n): Por Que Cada Elemento É Inserido e Removido No Máximo Uma Vez
A garantia de tempo O(n) dos algoritmos com pilha monotônica vem de um argumento simples de amortização: cada elemento é inserido na pilha exatamente uma vez e removido no máximo uma vez. Nenhum elemento pode ser inserido ou removido mais de uma vez. Portanto, o número total de operações de inserção + remoção em todo o laço é no máximo 2n, resultando em O(n) de trabalho total, embora o laço while aninhado pareça sugerir O(n²).
Essa análise amortizada é importante de explicar em entrevistas. O laço não é executado n vezes por iteração — ele é executado apenas o suficiente para remover os elementos que estavam aguardando, e esses elementos desaparecem para sempre depois de serem removidos.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nReconhecendo Problemas de Pilha Monotônica
É provável que um problema precise de uma pilha monotônica se solicitar o elemento maior ou menor mais próximo, a amplitude dos preços, os elementos visíveis em uma linha ou áreas baseadas em histogramas. Procure estas palavras-chave e padrões: cada elemento precisa da resposta do elemento relevante mais próximo em uma direção (à esquerda ou à direita).
Se uma solução de força bruta percorrer a partir de cada elemento para a esquerda ou para a direita (O(n²)), substitua essa busca por uma pilha monotônica. A pilha “lembra” as respostas candidatas, descarta as irrelevantes e remove a resposta correta exatamente no momento em que ela é necessária.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu que: uma pilha monotônica mantém uma ordem crescente ou decrescente removendo, antes da inserção, os elementos que violam a invariável; uma pilha decrescente responde sobre o elemento maior seguinte/anterior, enquanto uma pilha crescente responde sobre o elemento menor seguinte/anterior; e cada elemento é inserido e removido no máximo uma vez, resultando em tempo total O(n) — não O(n²). A seguir, aplicaremos a pilha monotônica para encontrar o maior retângulo em um histograma.
Perguntas Frequentes
A aula “Pilha monotônica: crescente vs decrescente” é grátis?
Sim — o texto completo de “Pilha monotônica: crescente vs decrescente” é 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 “Pilha monotônica: crescente vs decrescente”?
Mantenha uma pilha crescente ou decrescente para responder eficientemente a consultas sobre o próximo elemento maior e o elemento anterior menor 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 1 de 4.
Quanto tempo leva a aula “Pilha monotônica: crescente vs decrescente”?
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
- 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