O padrão em 30 segundos
Pilha: o último que entra é o primeiro que sai. Resolve tudo que tem estrutura de "abrir e fechar" ou "esperar o próximo maior". Parênteses válidos, expressões, monotonic stack para next-greater-element.
Como reconhecer na hora
- Parênteses/colchetes que precisam casar na ordem certa
- "Próximo elemento maior/menor à direita": monotonic stack
- Desfazer/voltar estado (undo, backtrack iterativo)
No monotonic stack, errar a direção da comparação (pilha com valores crescentes vs decrescentes; os índices guardados sempre crescem) e não conseguir explicar POR QUE cada elemento entra e sai no máximo uma vez, que é o argumento do O(n).
Complexidade típica: Na varredura com pilha monotônica, O(n) no total: cada elemento entra e sai no máximo uma vez. Conte também as outras etapas: Car Fleet custa O(n log n) pela ordenação. Generate Parentheses usa backtracking e, para n pares, custa O(n × Cₙ) para produzir as Cₙ combinações válidas (Cₙ é o número de Catalan).
Os 7 problemas da categoria
| Problema | Dificuldade | Nível no VagaGringa |
|---|---|---|
| Valid Parentheses cai muito | easy | nível 1 · core |
| Min Stack | medium | nível 3 |
| Evaluate Reverse Polish Notation | medium | nível 3 |
| Generate Parentheses | medium | nível 3 |
| Daily Temperatures | medium | nível 3 |
| Car Fleet | medium | nível 3 |
| Largest Rectangle in Histogram | hard | nível 4 |
No VagaGringa, esses 7 problemas entram numa trilha de 4 níveis com marcação do que mais cai em entrevista, e você registra tentativa, revisão e domínio de cada um.
Abrir a trilha NeetCode no app