Next Greater Element I
Você recebe dois arrays de inteiros distintos, nums1 e nums2, e todos os valores de nums1 também aparecem em nums2. O próximo elemento maior de um valor x é o primeiro valor à direita de x em nums2 que seja maior que x, ou -1 se não existir tal valor.
Retorne um array contendo o próximo elemento maior de cada valor de nums1, na ordem de nums1.
Função
- nums1integer-array
- os valores a serem respondidos, todos encontrados em nums2
- nums2integer-array
- o array no qual você procura à direita de cada valor
- Retornainteger-array
- o próximo elemento maior de cada valor de nums1, ou -1, na ordem de nums1
Restrições
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104- Todos os valores em
nums1são distintos, e todos os valores emnums2são distintos. - Todos os valores de
nums1aparecem emnums2.
Exemplos
- Entrada
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Saída
- [8, -1, 6]
- Explicação
- Depois do 3 em
nums2vêm 8 e 2, e 8 é o primeiro maior que 3. Depois do 8, vem apenas 2, então 8 recebe -1. O valor logo após 1 é 6, que já é maior.
- Entrada
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Saída
- [-1, 9]
- Explicação
- Apenas 4 vem depois de 5, e 4 é menor, então 5 recebe -1. O valor logo após 2 é 9. As respostas seguem a ordem de
nums1, não a ordem denums2.
- Entrada
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Saída
- [11, 10]
- Explicação
- O primeiro valor depois de 10 é 11. O primeiro valor depois de 0 é 10, que é maior, então 0 recebe 10, embora 11 venha depois e seja ainda maior.
+14 testes ocultos ao enviar
Para ir além
Para cada posição de nums2, você consegue retornar quantos passos à direita está seu próximo elemento maior, com a mesma passagem única?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Buscar à direita de cada valor de
nums1pode custar até 10^4 etapas por valor. As respostas dependem apenas denums2. Você consegue descobrir o próximo elemento maior de cada valor denums2em uma única passagem e, depois, consultar os valores denums1?Percorra
nums2da esquerda para a direita e mantenha os valores que ainda não encontraram um valor maior. Quando um novo valor chegar, ele será a resposta para cada valor menor que estiver aguardando. Os valores aguardando sempre formam uma sequência decrescente, então os menores ficam no topo de uma pilha.Para cada valor de
nums2: enquanto o topo da pilha for menor que ele, remova o elemento do topo e registre o valor atual como resposta em um mapa hash. Em seguida, empilhe o valor atual. No final, responda para cada valor denums1consultando o mapa, usando -1 para um valor que nunca foi removido da pilha.
Solução
Para um valor, a resposta é uma busca à direita dele, mas buscar para cada valor de nums1 pode custar até nums1.length × nums2.length etapas. As respostas dependem apenas de nums2, então você pode encontrar de uma só vez o próximo elemento maior de cada valor de nums2 usando uma pilha monotônica, armazenar esses resultados em um mapa hash e responder às consultas de nums1 por meio de buscas.
Encontre cada valor e percorra para a direita
Correta, mas não termina nos maiores testes
Intuição
Faça o que a definição diz. Para um valor x de nums1, percorra nums2 até chegar a x. Em seguida, continue percorrendo e pare no primeiro valor maior que x. Se chegar ao fim sem encontrar nenhum, a resposta é -1.
Isso está correto porque a varredura visita os valores à direita de x em ordem, então o primeiro valor maior que encontra é o primeiro valor maior que existe ali.
É lento quando as respostas estão distantes ou não existem. Se nums2 for decrescente, nenhuma varredura encontrará um valor maior, e cada valor de nums1 será percorrido até o fim. Com m valores em nums1 e n em nums2, isso pode levar até m × n etapas: 10^8 quando ambos os arrays contêm 10^4 valores. Cada varredura também percorre trechos que as varreduras anteriores já percorreram.
Algoritmo
- Percorra cada valor
xdenums1. - Encontre o índice
jem quenums2[j]é igual ax. - Percorra
nums2a partir dej+1e pare no primeiro valor maior quex. - Adicione esse valor ou -1 se a busca chegar ao fim.
- Retorne as respostas coletadas.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return resultPilha monotônica e um mapa de hash
Intuição
Inverta a pergunta. Em vez de perguntar, para cada valor, o que vem depois dele, percorra nums2 uma vez e deixe cada novo valor responder aos valores anteriores que ele supera. Mantenha em uma pilha os valores que ainda não têm resposta. Quando um valor chegar, remova do topo todos os valores menores: o novo valor é o primeiro maior à direita deles, portanto é a resposta. Em seguida, empilhe o novo valor, que ainda está aguardando sua própria resposta.
Percorra nums2 = [1, 6, 3, 8, 2]. Empilhe 1. Então chega 6 e supera 1, portanto 1 é mapeado para 6; empilhe 6. Então chega 3, que não supera 6, e é empilhado no topo: a pilha é [6, 3]. Então 8 remove 3 e 6, portanto ambos são mapeados para 8; empilhe 8. Em seguida, 2 é empilhado. A pilha termina como [8, 2], e esses dois valores não têm resposta. Para nums1 = [3, 8, 1], o mapa fornece [8, -1, 6].
A pilha é sempre decrescente da base para o topo, porque um valor só é empilhado depois que todos os valores menores acima dele foram removidos. É por isso que você só precisa olhar para o topo. Um valor sai da pilha no momento em que aparece o primeiro valor maior, então a resposta registrada é o primeiro, não o maior.
Cada valor de nums2 é empilhado uma vez e removido no máximo uma vez, então o loop interno realiza no máximo n remoções no total durante todo o percurso. Com as m consultas, o tempo é O(n + m). O mapa é o que conecta os dois arrays: os valores são distintos, então um valor é uma chave segura, embora ocupe posições diferentes em nums1 e nums2. As soluções em C e R usam um array de 10^4+1 posições indexado pelo valor como mapa, o que funciona porque nenhum valor excede 10^4.
Algoritmo
- Crie um mapa vazio e uma pilha vazia.
- Para cada valor de
nums2, remova da pilha todos os valores menores que estiverem no topo e associe-os ao valor atual no mapa. - Empilhe o valor atual.
- Para cada valor de
nums1, retorne a resposta associada a ele ou -1 se não houver nenhuma.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
Armadilhas e casos extremos
A pilha em si é um código curto; os erros estão no que você registra e em onde procura.
- Registrar o maior valor à direita em vez do primeiro maior. Em
nums2 = [3, 5, 1, 2, 4, 9, 0], a resposta para 1 é 2, não 9. - Retornar as respostas na ordem de
nums2ou para cada valor denums2. O resultado tem uma entrada para cada valor denums1, na ordem em que aparecem. - Retornar um índice em vez de um valor. O problema pede o próprio valor maior.
- Ler
nums2no índice que um valor tem emnums1. O mesmo valor ocupa posições diferentes nos dois arrays; encontre-o pelo valor, que é para isso que serve o mapa. - Esquecer os valores que permanecem na pilha no final. Eles nunca encontraram um valor maior, então sua resposta é -1; uma consulta ao mapa sem valor padrão falha ou não retorna nada para eles.
- Procurar à esquerda ou dar a volta até o início de
nums2. Apenas os valores à direita contam, e o array não dá a volta.
Perguntas frequentes4
Qual é a complexidade de tempo do Next Greater Element I?
A solução com pilha monotônica é executada em O(n + m) tempo, em que n é o comprimento de nums2 e m é o comprimento de nums1. Cada valor de nums2 é empilhado e desempilhado no máximo uma vez, e cada valor de nums1 corresponde a uma consulta no mapa. O mapa e a pilha usam O(n) de espaço. Percorrer para a direita a partir de cada valor leva O(n·m) tempo.
O que é uma pilha monotônica?
É uma pilha cujos valores permanecem ordenados de baixo para cima, neste caso em ordem decrescente. Antes de inserir um novo valor, você remove tudo o que quebraria a ordem, e é nessas remoções que o trabalho acontece: cada valor removido encontrou seu primeiro valor maior à direita. Ela resolve questões sobre o próximo maior, o próximo menor e outras semelhantes em tempo linear.
Por que Next Greater Element I precisa de um mapa de hash?
A percorrida pela pilha produz as respostas na ordem em que os valores saem da pilha, associadas aos valores de nums2. A saída deve seguir a ordem de nums1, em que os mesmos valores estão em outras posições. Como todos os valores são distintos, um mapa de valores para respostas conecta os dois arrays com uma consulta de tempo constante por valor.
O que muda se nums2 for circular?
Então, a busca por um valor maior pode continuar a partir do início do array. Percorra o array duas vezes usando a mesma pilha, com o índice i % n para i de 0 a 2n-1, e empilhe valores apenas durante a primeira rodada. Os valores que ainda estiverem na pilha após as duas rodadas não têm nenhum valor maior em lugar algum, então a resposta para eles é -1.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def nextGreaterElement(nums1, nums2):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Esperado
[8, -1, 6]