Pular para o conteúdo

Busca do próximo valor maior

Fácil#monotonic-stack#hash-map~15 min

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

Tempo-alvo
O(n + q)
Espaço-alvo
O(n + q)

Restrições

  • nums holds distinct integers
  • every query value appears in nums

Travou na ideia, e não no código? Pilha monotônica explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado