Busca do próximo valor maior
A missão
Problema
Você recebe uma lista nums de inteiros distintos e uma lista queries cujos valores aparecem todos em algum lugar de nums. Para cada valor de consulta (query), encontre o primeiro valor à direita dele em nums que seja maior, ou -1 quando nenhum valor maior vier depois. Retorne as respostas na ordem das consultas.
Exemplos
Input: nums = [4, 1, 3, 6, 2, 5], queries = [1, 3, 2, 6]
Output: [3, 6, 5, -1]
Por quê: 1 é seguido por 3, 3 por 6 e 2 por 5, enquanto nada depois do 6 é maior
Input: nums = [5, 4, 3, 2, 1], queries = [4, 1]
Output: [-1, -1]
Por quê: a lista só cai, então nenhum valor tem um maior depois dele
Input: nums = [7], queries = [7]
Output: [-1]
Por quê: edge case: um único valor não tem nada à direita
Dicas
0 / 3
Varrer para a direita a partir de cada consulta funciona, mas fica quadrático quando muitos valores esperam muito tempo por algo maior. Uma única passada sobre nums consegue responder todos os valores de uma vez?
Guarde os valores que ainda esperam um maior. Quando chega um valor novo, todo valor em espera menor que ele acaba de achar a resposta. Os valores em espera sempre formam uma sequência decrescente, então os menores ficam no topo.
Percorra nums com uma pilha. Enquanto o topo da pilha for menor que o valor atual, desempilhe-o (pop) e registre o valor atual como a resposta dele em um dicionário. Empilhe (push) o valor atual. No final, busque cada consulta no dicionário, com -1 como padrão.
- Tempo-alvo
- O(n + q)
- Espaço-alvo
- O(n + q)
Restrições
- nums holds distinct integers
- every query value appears in nums
Solução
Um valor espera na pilha até chegar o primeiro valor maior, e nesse momento ele está no topo, porque qualquer valor empilhado depois dele e ainda em espera é menor que ele. Então uma única passada da esquerda para a direita desempilha cada valor exatamente quando a resposta dele aparece e registra o par em um dicionário, e o que ainda está na pilha no final nunca recebeu resposta. As consultas viram, então, simples buscas no dicionário. Cada valor é empilhado e desempilhado no máximo uma vez, então o tempo é O(n + q) e o espaço é O(n).
def next_greater_lookup(nums, queries):
answer = {}
stack = [] # waiting values, falling from bottom to top
for x in nums:
while stack and stack[-1] < x:
answer[stack.pop()] = x # x is the first larger value after it
stack.append(x)
return [answer.get(q, -1) for q in queries]
print(next_greater_lookup([4, 1, 3, 6, 2, 5], [1, 3, 2, 6])) # -> [3, 6, 5, -1]
print(next_greater_lookup([5, 4, 3, 2, 1], [4, 1])) # -> [-1, -1]
print(next_greater_lookup([7], [7])) # -> [-1]Travou na ideia, e não no código? Pilha monotônica explica isso.