Pilha Monotônica: Próximo Elemento Maior
Responda a consultas de extensão em uma única passagem.
Pilha Monotônica: Próximo Elemento Maior é uma aula grátis de Coding 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 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 problema do próximo maior
Para cada número, você quer o primeiro valor maior à sua direita. A força bruta custa O(n ao quadrado), mas uma pilha monótona resolve isso em uma única passagem.
O que significa monótona
Uma pilha monótona mantém seus values em ordem, neste caso decrescente. Assim, no momento em que essa ordem seria quebrada, sabemos que uma resposta foi encontrada.
Armazene índices, não valores
Empilhe índices em vez dos números propriamente ditos. Dessa forma, você sabe exatamente qual posição preencher quando surgir um elemento maior.
stack = []
ans = [-1] * len(nums)Percorra da esquerda para a direita
Percorra a matriz uma única vez. Em cada índice, você removerá itens já resolvidos ou empilhará o índice atual para mais tarde.
for i in range(len(nums)):Remova os menores
Enquanto o valor atual for maior que o valor no índice do topo, esse índice finalmente encontrou seu próximo elemento maior.
while stack and nums[i] > nums[stack[-1]]:Registre a resposta
Remova o índice do topo e defina sua resposta como o valor atual. Cada índice é resolvido exatamente uma vez, mantendo o trabalho linear.
j = stack.pop()
ans[j] = nums[i]Empilhe e continue
Depois de resolver tudo que for menor, empilhe o índice atual para que ele aguarde seu próprio elemento maior futuro.
stack.append(i)Os restantes não têm resposta
Os índices que ainda estão na pilha ao final nunca encontraram um valor maior. Eles mantêm o valor padrão -1, indicando que nenhum existe.
Por que é O(n)
Cada índice é empilhado uma vez e removido uma vez. Mesmo com o laço while interno, o trabalho total permanece linear em toda a varredura.
Inverta para encontrar o próximo menor
Precisa do próximo elemento menor? Mantenha a pilha crescente, invertendo a comparação de maior que para menor que.
while stack and nums[i] < nums[stack[-1]]:Um padrão, não um truque
Consultas de intervalo, preços de ações e áreas de histogramas reutilizam essa ideia. A pilha monótona é um padrão essencial de competições que vale a pena memorizar.
Verificação rápida
Você resolve o problema do próximo elemento maior com uma pilha monótona. Por que o tempo total é linear?
Recapitulação: uma passagem, muitas respostas
Você usou uma pilha monótona decrescente de índices para encontrar os próximos elementos maiores em O(n). Esse padrão desbloqueia muitos problemas de intervalo. 🚀
Perguntas Frequentes
A aula “Pilha Monotônica: Próximo Elemento Maior” é grátis?
Sim — o texto completo de “Pilha Monotônica: Próximo Elemento Maior” é 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: Próximo Elemento Maior”?
Responda a consultas de extensão em uma única passagem. 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 2 de 4.
Quanto tempo leva a aula “Pilha Monotônica: Próximo Elemento Maior”?
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
- Pilhas para Correspondência de Parênteses
- Pilha Monotônica: Próximo Elemento Maior
- Filas e collections.deque
- Máximo em Janela Deslizante com Deque