O padrão em 30 segundos
Tomar a melhor decisão local e nunca olhar pra trás. Só funciona quando o problema tem estrutura que GARANTE que o ótimo local leva ao global, e a entrevista avalia exatamente se você sabe argumentar essa garantia.
Como reconhecer na hora
- "Máximo que você consegue com escolhas em sequência" (jump game, gas station)
- Ordenar por algum critério e processar em ordem resolve
- Kadane: melhor subarray com "zera quando fica negativo"
onde todo mundo erra · anotado no caderno
Aplicar greedy sem justificar por que não perde a solução ótima. Em metade dos problemas parecidos o greedy está ERRADO e a resposta é DP. Dizer "greedy funciona aqui porque..." é o que o entrevistador quer ouvir.
Complexidade típica: Em geral O(n) ou O(n log n) quando precisa ordenar primeiro.
Os 8 problemas da categoria
| Problema | Dificuldade | Nível no app |
|---|---|---|
| Maximum Subarray cai muito | medium | nível 2 · core |
| Jump Game cai muito | medium | nível 2 · core |
| Jump Game II | medium | nível 3 |
| Gas Station | medium | nível 3 |
| Hand of Straights | medium | nível 3 |
| Merge Triplets to Form Target Triplet | medium | nível 3 |
| Partition Labels | medium | nível 3 |
| Valid Parenthesis String | medium | nível 3 |
No app, esses 8 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