Find Peak Element
O array nums sobe e depois desce: cada valor é maior que o anterior até certo índice, e cada valor após esse índice é menor que o anterior. Qualquer uma das partes pode estar vazia, então o array pode apenas subir ou apenas descer. O valor no índice de virada é o pico, o único valor maior que todos os seus vizinhos.
Retorne o índice do pico em tempo O(log n).
Função
- numsinteger-array
- os valores aumentam até atingir um pico e depois diminuem
- Retornainteger
- o índice do pico
Restrições
1 ≤ nums.length ≤ 5000-106 ≤ nums[i] ≤ 106nums[i] != nums[i+1]para todoiválido.numsaumenta estritamente até um índice e diminui estritamente depois dele, então há exatamente um pico.
Exemplos
- Entrada
- nums = [2, 5, 9, 4, 1]
- Saída
- 2
- Explicação
- Os valores sobem passando por 2, 5 e 9, depois caem passando por 4 e 1. A inversão ocorre em 9, índice 2.
- Entrada
- nums = [8, 6, 3, -2]
- Saída
- 0
- Explicação
- O array só desce, então a parte crescente está vazia e o pico é o primeiro valor, 8 no índice 0.
- Entrada
- nums = [-7, -3, 0, 12, 40]
- Saída
- 4
- Explicação
- O array só cresce, então o pico é o último valor, 40 no índice 4. Valores negativos não mudam nada.
Para ir além
Em uma grade na qual nenhuma célula vizinha é igual a outra, um pico é uma célula maior que suas até quatro vizinhas. Você consegue encontrar um sem ler todas as células?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Escolha qualquer índice
mide observenums[mid+1]. O que a direção desse passo indica sobre onde está o pico?Um passo para cima só acontece antes do pico, e um passo para baixo só no pico ou depois dele. Portanto, uma comparação elimina um dos lados de
mid.Mantenha um intervalo que sempre contenha o pico. Em uma subida, mova
loparamid+1; caso contrário, movahiparamid. Pare quando eles se encontrarem.
Solução
Com um único pico, ele é o maior valor, então uma única passagem o encontra em O(n). Para O(log n), compare nums[mid] com nums[mid+1]: a inclinação em mid indica de que lado do pico ele está, então a cada etapa é possível descartar metade do intervalo.
Caminhe até que os valores comecem a diminuir
Intuição
Antes do pico, cada valor é menor que o próximo, e, a partir do pico, cada valor é maior. Portanto, o pico é o primeiro índice i em que nums[i] > nums[i+1], ou o último índice se o array só cresce.
Quando o pico está no fim de 5000 valores, o percurso faz 4999 comparações, enquanto a busca binária precisa de 13.
Algoritmo
- Para
ide 0 an-2, comparenums[i]comnums[i+1]. - No primeiro
iem quenums[i]for maior, retornei. - Se o loop terminar sem uma queda, retorne
n-1.
def findPeakElement(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i # the first step down starts at the peak
return len(nums) - 1 # never went down: the last value is the peakBusca binária na inclinação
Intuição
Leia um par, nums[mid] e nums[mid+1]. Uma subida significa que o array ainda está subindo, o que neste array acontece apenas antes do pico: o pico está em mid+1 ou à direita dele. Uma descida significa que você está no pico ou já passou por ele: o pico está em mid ou à esquerda dele.
Mantenha um intervalo [lo, hi] que sempre contém o pico. Uma subida move lo para mid+1. Uma descida move hi para mid, mantendo mid porque ele pode ser o pico. Quando lo encontra hi, o único índice restante é o pico. Arredondar mid para baixo o mantém abaixo de hi, então mid+1 sempre existe.
No primeiro exemplo, mid = 2 vê 9 > 4, então hi = 2; depois, mid = 1 vê 5 < 9, então lo = 2, o pico. 5000 valores levam no máximo 13 passos.
Algoritmo
- Defina
lo = 0ehi = n-1. - Enquanto
lo < hi, calculemid = lo + (hi - lo) / 2, arredondado para baixo. - Se
nums[mid] < nums[mid+1], definalo = mid + 1. - Caso contrário, defina
hi = mid. - Retorne
lo.
def findPeakElement(nums):
lo, hi = 0, len(nums) - 1 # the peak is always inside [lo, hi]
while lo < hi:
mid = lo + (hi - lo) // 2 # mid < hi, so mid + 1 is a valid index
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # still climbing: the peak is to the right of mid
else:
hi = mid # going down: the peak is mid or to its left
return lo
Armadilhas e casos extremos
- Definir
hi = mid - 1ao dar um passo para baixo. Em[2, 5, 9, 4, 1], o primeiromidé o próprio pico, ehi = 1o descarta; a busca retorna 1. - Comparar com
nums[mid-1]enquanto se arredondamidpara baixo.midpode ser 0, caso em que não há vizinho à esquerda. - Usar um intervalo semiaberto com
hi = n. Entãomidpode sern-1, enums[mid+1]acessa uma posição além do fim, imediatamente no caso de um único valor. - Esquecer o deslocamento em Lua e R. A resposta ainda é o índice baseado em 0, então uma posição
ié retornada comoi-1.
Perguntas frequentes3
Qual é a complexidade de tempo de Find Peak Element?
A busca binária é executada em tempo O(log n) e espaço O(1), em no máximo 13 etapas para 5000 valores. A varredura a partir da esquerda é O(n), pois pode ler todos os pares antes de encontrar a queda.
A busca binária ainda funciona quando há vários picos?
Sim, desde que os vizinhos sejam diferentes e os pontos além das duas extremidades sejam considerados menores que qualquer valor. Ela retorna um pico, não necessariamente o mais alto. Depois de um passo para cima, os valores precisam começar a cair até o fim do intervalo, no máximo, e a primeira mudança de direção é um pico, então o lado que a busca mantém sempre contém um.
O pico é sempre o maior valor?
Neste problema, sim: o array sobe até um pico e cai depois dele, então nada mais pode ser maior. Na versão com vários picos, não é assim, pois qualquer valor maior que os dois vizinhos conta. É por isso que a busca compara os vizinhos em vez de procurar o máximo.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def findPeakElement(nums):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
nums = [2, 5, 9, 4, 1]
Saída Esperada
2