Tratemos de explorar este problema en profundidad.
Decimos que un elemento es un elemento Peak si no es más pequeño que sus elementos vecinos. Puede haber más de un elemento pico.
por ejemplo, que Arr [] = {12,34,54,30,23,98,21} . que los elementos pico son 54 y 98 .
- Cómo explicar el algoritmo de clasificación de inserción a un niño de 10 años
- Cómo imprimir rutas en forma DFS en gráficos
- ¿Cómo puede alguien calcular la complejidad de este algoritmo?
- Cuando quitamos un borde de un árbol, parece obvio que nos quedan dos árboles, pero ¿cómo podríamos probar esto?
- ¿Cuál es la mejor manera de aprender la estructura de datos y el algoritmo para un programador promedio?
al encontrar elementos de pico para el elemento de esquina solo consideramos un elemento vecino inmediato.
estamos interesados en encontrar a cualquiera elemento pico.
Existen varios casos según la naturaleza de los elementos:
caso 1: cuando los elementos se ordenan en orden creciente
En este caso, el último elemento es siempre el elemento pico.
por ejemplo Arr [] = {1,2,3,4,5} el elemento pico es 5. Como 5 es mayor que 4.
caso 2: cuando los elementos se ordenan en orden decreciente.
En este caso, el primer elemento es siempre un elemento pico.
por ejemplo arr [] = {50,40,30,20,2} el elemento pico es 50.
caso 3: cuando todos los elementos de entrada son iguales.
En este caso, cada elemento es un elemento pico ya que todos los elementos no son más pequeños que sus elementos vecinos.
por ejemplo arr [] = {2,2,2,2,2,2,2,2} todos son elementos de pico.
caso 4: cuando los elementos de entrada están en orden aleatorio.
En este caso, dado que estamos interesados en encontrar cualquier elemento pico no necesariamente todos. Podemos observar fácilmente que alguna parte de la matriz de entrada caerá en cualquiera de los casos discutidos anteriormente.
por ejemplo arr [] = {12,34,54,30,23,98,21} en esta matriz podemos ver fácilmente que alguna parte de la matriz tiene una situación de caso 1 y otra parte tiene una situación de caso 2, es decir, del índice 0 a índice 2, esta submatriz tiene la situación del caso 1 ( orden creciente ) del índice 2 al índice 4, esta parte de la matriz tiene la situación del caso 2 (orden decreciente) .
así que hay una transición en la forma del índice 2 que aumenta o disminuye si dibujamos su gráfico, entonces podemos visualizarlo fácilmente. Este será un elemento pico. explicación similar para el elemento pico 98.
Entonces, a partir de la discusión y los ejemplos anteriores, queda claro que siempre hay un elemento pico en una matriz. a pesar de la naturaleza de la matriz.
Creo que obtendrás algo de intuición detrás de esto.