Find Peak Element

Q: ¿Cuál es la complejidad temporal de Find Peak Element?

La búsqueda binaria se ejecuta en tiempo O(log n) y espacio O(1) , en un máximo de 13 pasos para 5000 valores. El recorrido desde la izquierda es O(n) , ya que puede leer cada par antes de encontrar la caída.

Q: ¿Sigue funcionando la búsqueda binaria cuando hay varios picos?

Sí, siempre que los vecinos sean distintos y los lugares más allá de ambos extremos cuenten como inferiores a cualquier valor. Devuelve un pico, no siempre el más alto. Después de un ascenso, los valores deben empezar a descender, como muy tarde, al final del rango, y el primer cambio de dirección es un pico, así que el lado que conserva la búsqueda siempre contiene uno.

Q: ¿El pico es siempre el valor más grande?

En este problema, sí: el arreglo sube hasta un pico y baja después, así que nada más puede ser mayor. En la versión con varios picos, no es así, ya que cualquier valor mayor que sus dos vecinos cuenta. Por eso la búsqueda compara los vecinos en lugar de buscar el máximo.

MedioBúsqueda binaria

+10

El array nums sube y después baja: cada valor es mayor que el anterior hasta cierto índice, y cada valor después de ese índice es menor que el anterior. Cualquiera de las dos partes puede estar vacía, así que el array puede solo subir o solo bajar. El valor en el índice de giro es el pico, el único valor mayor que todos sus vecinos.

Devuelve el índice del pico en tiempo O(log n).

Función

findPeakElement(nums: integer-array) → integer

numsinteger-array: los valores, subiendo hasta un máximo y después bajando
Devuelveinteger: el índice del pico

Restricciones

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] para cada i válido.
nums aumenta estrictamente hasta un índice y disminuye estrictamente después, así que hay exactamente un pico.

Ejemplos

Entrada: nums = [2, 5, 9, 4, 1]
Salida: 2
Explicación: Los valores suben pasando por 2, 5 y 9, y después bajan pasando por 4 y 1. El cambio de dirección está en 9, índice 2.

Para ir más allá

En una cuadrícula donde no hay dos celdas vecinas iguales, un pico es una celda mayor que sus hasta cuatro vecinas. ¿Puedes encontrar uno sin leer todas las celdas?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Con un único pico, el pico es el valor más grande, así que una pasada lo encuentra en O(n). Para O(log n), compara nums[mid] con nums[mid+1]: la pendiente en mid te indica en qué lado del pico se encuentra, así que en cada paso puedes descartar la mitad del intervalo.

Camina hasta que los valores empiecen a disminuir

Intuición

Antes del pico, cada valor es menor que el siguiente, y a partir del pico cada valor es mayor. Así que el pico es el primer índice i donde nums[i] > nums[i+1], o el último índice si el arreglo solo aumenta.

Cuando el pico está al final de 5000 valores, el recorrido realiza 4999 comparaciones, mientras que la búsqueda binaria necesita 13.

Algoritmo

Para i desde 0 hasta n-2, compara nums[i] con nums[i+1].
En el primer i donde nums[i] sea mayor, devuelve i.
Si el bucle termina sin encontrar una caída, devuelve 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 peak

Búsqueda binaria en la pendiente

Intuición

Lee un par, nums[mid] y nums[mid+1]. Un paso hacia arriba significa que el arreglo sigue ascendiendo, lo que en este arreglo sucede solo antes del pico: el pico está en mid+1 o a su derecha. Un paso hacia abajo significa que estás en el pico o más allá: el pico está en mid o a su izquierda.

Mantén un intervalo [lo, hi] que siempre contenga el pico. Un paso hacia arriba mueve lo a mid+1. Un paso hacia abajo mueve hi a mid, manteniendo mid porque podría ser el pico. Cuando lo llega a hi, el índice que queda es el pico. Redondear mid hacia abajo hace que quede por debajo de hi, así que mid+1 siempre existe.

En el primer ejemplo, mid = 2 ve 9 > 4, así que hi = 2; después, mid = 1 ve 5 < 9, así que lo = 2, el pico. 5000 valores requieren como máximo 13 pasos.

Algoritmo

Establece lo = 0 y hi = n-1.
Mientras lo < hi, toma mid = lo + (hi - lo) / 2, redondeado hacia abajo.
Si nums[mid] < nums[mid+1], establece lo = mid + 1.
De lo contrario, establece hi = mid.
Devuelve 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

Errores comunes y casos límite

Asignar hi = mid - 1 al dar un paso hacia abajo. En [2, 5, 9, 4, 1], el primer mid es el pico mismo, y hi = 1 lo descarta; la búsqueda devuelve 1.
Comparar con nums[mid-1] mientras se redondea mid hacia abajo. mid puede ser 0, donde no hay ningún vecino a la izquierda.
Usar un rango semiabierto con hi = n. Después, mid puede ser n-1, y nums[mid+1] accede a una posición fuera del final, incluso con un único valor.
Olvidar el desplazamiento en Lua y R. La respuesta sigue siendo el índice basado en 0, así que la posición i se devuelve como i-1.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Find Peak Element?

La búsqueda binaria se ejecuta en tiempo O(log n) y espacio O(1), en un máximo de 13 pasos para 5000 valores. El recorrido desde la izquierda es O(n), ya que puede leer cada par antes de encontrar la caída.

¿Sigue funcionando la búsqueda binaria cuando hay varios picos?

Sí, siempre que los vecinos sean distintos y los lugares más allá de ambos extremos cuenten como inferiores a cualquier valor. Devuelve un pico, no siempre el más alto. Después de un ascenso, los valores deben empezar a descender, como muy tarde, al final del rango, y el primer cambio de dirección es un pico, así que el lado que conserva la búsqueda siempre contiene uno.

¿El pico es siempre el valor más grande?

En este problema, sí: el arreglo sube hasta un pico y baja después, así que nada más puede ser mayor. En la versión con varios picos, no es así, ya que cualquier valor mayor que sus dos vecinos cuenta. Por eso la búsqueda compara los vecinos en lugar de buscar el máximo.

def findPeakElement(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [2, 5, 9, 4, 1]

Salida Esperada