Encuentre un elemento de pico en una array 2D

Un elemento es un elemento pico si es mayor o igual que sus cuatro vecinos, izquierdo, derecho, superior e inferior. Por ejemplo, los vecinos de A[i][j] son ​​A[i-1][j], A[i+1][j], A[i][j-1] y A[i][j+1 ]. Para los elementos de esquina, los vecinos que faltan se consideran de valor infinito negativo.

Ejemplos: 

Input : 10 20 15
        21 30 14
        7  16 32 
Output : 30
30 is a peak element because all its 
neighbors are smaller or equal to it. 
32 can also be picked as a peak.

Input : 10 7
        11 17
Output : 17

A continuación se presentan algunos datos sobre este problema: 

1.  Una Diagonal adyacente no se considera como vecina. 
2. Un elemento pico no es necesariamente el elemento máximo. 
3. Puede existir más de uno de estos elementos. 
4. Siempre hay un elemento cumbre. Podemos ver esta propiedad creando algunas arrays con lápiz y papel.

Método 1: (Fuerza bruta)  :

Iterar a través de todos los elementos de Matrix y verificar si es mayor/igual a todos sus vecinos. En caso afirmativo, devuelva el elemento.
Complejidad de tiempo: O(filas * columnas) 
Espacio auxiliar: O(1)

Método 2: (Eficiente):

Este problema es principalmente una extensión de Find a peak element in 1D array . Aplicamos una solución similar basada en búsqueda binaria aquí. 

1. Considere la mitad de la columna y encuentre el elemento máximo en ella.
2. Deje que el índice de la mitad de la columna sea ‘mid’, el valor del elemento máximo en la mitad de la columna sea ‘max’ y el elemento máximo esté en ‘mat[max_index][mid]’. 
3. Si max >= A[index][mid-1] & max >= A[index][pick+1], max es un pico, devuelve max.
4. Si max < mat[max_index][mid-1], se repite para la mitad izquierda de la array.
5. Si max < mat[max_index][mid+1], se repite para la mitad derecha de la array.

A continuación se muestra la implementación del algoritmo anterior: 

// Finding peak element in a 2D Array.
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 100;
 
// Function to find the maximum in column 'mid'
// 'rows' is number of rows.
int findMax(int arr[][MAX], int rows, int mid, int& max)
{
    int max_index = 0;
    for (int i = 0; i < rows; i++) {
        if (max < arr[i][mid]) {
            // Saving global maximum and its index
            // to check its neighbours
            max = arr[i][mid];
            max_index = i;
        }
    }
    return max_index;
}
 
// Function to find a peak element
int findPeakRec(int arr[][MAX], int rows, int columns,
                int mid)
{
    // Evaluating maximum of mid column. Note max is
    // passed by reference.
    int max = 0;
    int max_index = findMax(arr, rows, mid, max);
 
    // If we are on the first or last column,
    // max is a peak
    if (mid == 0 || mid == columns - 1)
        return max;
 
    // If mid column maximum is also peak
    if (max >= arr[max_index][mid - 1] && max >= arr[max_index][mid + 1])
        return max;
 
    // If max is less than its left
    if (max < arr[max_index][mid - 1])
        return findPeakRec(arr, rows, columns, mid - ceil((double)mid / 2));
 
    // If max is less than its left
    // if (max < arr[max_index][mid+1])
    return findPeakRec(arr, rows, columns, mid + ceil((double)mid / 2));
}
 
// A wrapper over findPeakRec()
int findPeak(int arr[][MAX], int rows, int columns)
{
    return findPeakRec(arr, rows, columns, columns / 2);
}
 
// Driver Code
int main()
{
    int arr[][MAX] = { { 10, 8, 10, 10 },
                       { 14, 13, 12, 11 },
                       { 15, 9, 11, 21 },
                       { 16, 17, 19, 20 } };
 
    // Number of Columns
    int rows = 4, columns = 4;
    cout << findPeak(arr, rows, columns);
    return 0;
}

// Finding peak element in a 2D Array.
class GFG
{
    static int MAX = 100;
 
    // Function to find the maximum in column
    // 'mid', 'rows' is number of rows.
    static int findMax(int[][] arr, int rows,
                       int mid, int max)
    {
        int max_index = 0;
        for (int i = 0; i < rows; i++)
        {
            if (max < arr[i][mid])
            {
                 
                // Saving global maximum and its index
                // to check its neighbours
                max = arr[i][mid];
                max_index = i;
            }
        }
        return max_index;
    }
 
    // Function to change the value of [max]
    static int Max(int[][] arr, int rows,
                   int mid, int max)
    {
        for (int i = 0; i < rows; i++)
        {
            if (max < arr[i][mid])
            {
                 
                // Saving global maximum and its index
                // to check its neighbours
                max = arr[i][mid];
            }
        }
        return max;
    }
 
    // Function to find a peak element
    static int findPeakRec(int[][] arr, int rows,
                           int columns, int mid)
    {
        // Evaluating maximum of mid column.
        // Note max is passed by reference.
        int max = 0;
        int max_index = findMax(arr, rows, mid, max);
        max = Max(arr, rows, mid, max);
 
        // If we are on the first or last column,
        // max is a peak
        if (mid == 0 || mid == columns - 1)
            return max;
 
        // If mid column maximum is also peak
        if (max >= arr[max_index][mid - 1] &&
            max >= arr[max_index][mid + 1])
            return max;
 
        // If max is less than its left
        if (max < arr[max_index][mid - 1])
            return findPeakRec(arr, rows, columns,
                         (int)(mid - Math.ceil((double) mid / 2)));
 
        // If max is less than its left
        // if (max < arr[max_index][mid+1])
        return findPeakRec(arr, rows, columns,
                     (int)(mid + Math.ceil((double) mid / 2)));
    }
 
    // A wrapper over findPeakRec()
    static int findPeak(int[][] arr, int rows, int columns)
    {
        return findPeakRec(arr, rows, columns, columns / 2);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[][] arr = {{ 10, 8, 10, 10 },
                       { 14, 13, 12, 11 },
                       { 15, 9, 11, 21 },
                       { 16, 17, 19, 20 }};
         
        // Number of Columns
        int rows = 4, columns = 4;
        System.out.println(findPeak(arr, rows, columns));
    }
}
 
// This code is contributed by
// sanjeev2552

# Finding peak element in a 2D Array.
MAX = 100
from math import ceil
 
# Function to find the maximum in column 'mid'
# 'rows' is number of rows.
def findMax(arr, rows, mid,max):
 
    max_index = 0
    for i in range(rows):
        if (max < arr[i][mid]):
             
            # Saving global maximum and its index
            # to check its neighbours
            max = arr[i][mid]
            max_index = i
    #print(max_index)
 
    return max,max_index
 
# Function to find a peak element
def findPeakRec(arr, rows, columns,mid):
 
    # Evaluating maximum of mid column.
    # Note max is passed by reference.
    max = 0
    max, max_index = findMax(arr, rows, mid, max)
 
    # If we are on the first or last column,
    # max is a peak
    if (mid == 0 or mid == columns - 1):
        return max
 
    # If mid column maximum is also peak
    if (max >= arr[max_index][mid - 1] and
        max >= arr[max_index][mid + 1]):
        return max
 
    # If max is less than its left
    if (max < arr[max_index][mid - 1]):
        return findPeakRec(arr, rows, columns,
                           mid - ceil(mid / 2.0))
 
    # If max is less than its left
    # if (max < arr[max_index][mid+1])
    return findPeakRec(arr, rows, columns,
                       mid + ceil(mid / 2.0))
 
# A wrapper over findPeakRec()
def findPeak(arr, rows, columns):
    return findPeakRec(arr, rows,
                       columns, columns // 2)
 
# Driver Code
arr = [ [ 10, 8, 10, 10 ],
        [ 14, 13, 12, 11 ],
        [ 15, 9, 11, 21 ],
        [ 16, 17, 19, 20 ] ]
 
# Number of Columns
rows = 4
columns = 4
print(findPeak(arr, rows, columns))
 
# This code is contributed by Mohit Kumar

// Finding peak element in a 2D Array.
using System;
 
class GFG
{
 
    // Function to find the maximum in column
    // 'mid', 'rows' is number of rows.
    static int findMax(int[,] arr, int rows,
                       int mid, int max)
    {
        int max_index = 0;
        for (int i = 0; i < rows; i++)
        {
            if (max < arr[i,mid])
            {
                 
                // Saving global maximum and its
                // index to check its neighbours
                max = arr[i,mid];
                max_index = i;
            }
        }
        return max_index;
    }
 
    // Function to change the value of [max]
    static int Max(int[,] arr, int rows,
                   int mid, int max)
    {
        for (int i = 0; i < rows; i++)
        {
            if (max < arr[i, mid])
            {
                 
                // Saving global maximum and its
                // index to check its neighbours
                max = arr[i, mid];
            }
        }
        return max;
    }
 
    // Function to find a peak element
    static int findPeakRec(int[,] arr, int rows,
                           int columns, int mid)
    {
        // Evaluating maximum of mid column.
        // Note max is passed by reference.
        int max = 0;
        int max_index = findMax(arr, rows, mid, max);
        max = Max(arr, rows, mid, max);
 
        // If we are on the first or last column,
        // max is a peak
        if (mid == 0 || mid == columns - 1)
            return max;
 
        // If mid column maximum is also peak
        if (max >= arr[max_index, mid - 1] &&
            max >= arr[max_index, mid + 1])
            return max;
 
        // If max is less than its left
        if (max < arr[max_index,mid - 1])
            return findPeakRec(arr, rows, columns,
                   (int)(mid - Math.Ceiling((double) mid / 2)));
 
        // If max is less than its left
        // if (max < arr[max_index][mid+1])
        return findPeakRec(arr, rows, columns,
               (int)(mid + Math.Ceiling((double) mid / 2)));
    }
 
    // A wrapper over findPeakRec()
    static int findPeak(int[,] arr,
                        int rows, int columns)
    {
        return findPeakRec(arr, rows, columns,
                                      columns / 2);
    }
 
    // Driver Code
    static public void Main ()
    {
        int[,] arr = {{ 10, 8, 10, 10 },
                      { 14, 13, 12, 11 },
                      { 15, 9, 11, 21 },
                      { 16, 17, 19, 20 }};
     
        // Number of Columns
        int rows = 4, columns = 4;
        Console.Write(findPeak(arr, rows, columns));
    }
}
 
// This code is contributed by ajit.

<script>
    // Finding peak element in a 2D Array.
     
    let MAX = 100;
   
    // Function to find the maximum in column
    // 'mid', 'rows' is number of rows.
    function findMax(arr, rows, mid, max)
    {
        let max_index = 0;
        for (let i = 0; i < rows; i++)
        {
            if (max < arr[i][mid])
            {
                   
                // Saving global maximum and its index
                // to check its neighbours
                max = arr[i][mid];
                max_index = i;
            }
        }
        return max_index;
    }
   
    // Function to change the value of [max]
    function Max(arr, rows, mid, max)
    {
        for (let i = 0; i < rows; i++)
        {
            if (max < arr[i][mid])
            {
                   
                // Saving global maximum and its index
                // to check its neighbours
                max = arr[i][mid];
            }
        }
        return max;
    }
   
    // Function to find a peak element
    function findPeakRec(arr, rows, columns, mid)
    {
        // Evaluating maximum of mid column.
        // Note max is passed by reference.
        let max = 0;
        let max_index = findMax(arr, rows, mid, max);
        max = Max(arr, rows, mid, max);
   
        // If we are on the first or last column,
        // max is a peak
        if (mid == 0 || mid == columns - 1)
            return max;
   
        // If mid column maximum is also peak
        if (max >= arr[max_index][mid - 1] &&
            max >= arr[max_index][mid + 1])
            return max;
   
        // If max is less than its left
        if (max < arr[max_index][mid - 1])
            return findPeakRec(arr, rows, columns, (mid - Math.ceil(mid / 2)));
   
        // If max is less than its left
        // if (max < arr[max_index][mid+1])
        return findPeakRec(arr, rows, columns, (mid + Math.ceil(mid / 2)));
    }
   
    // A wrapper over findPeakRec()
    function findPeak(arr, rows, columns)
    {
        return findPeakRec(arr, rows, columns, parseInt(columns / 2, 10));
    }
     
    let arr = [[ 10, 8, 10, 10 ],
                [ 14, 13, 12, 11 ],
                [ 15, 9, 11, 21 ],
                [ 16, 17, 19, 20 ]];
           
    // Number of Columns
    let rows = 4, columns = 4;
    document.write(findPeak(arr, rows, columns));
 
</script>

21

Complejidad de tiempo: O(filas * registro(columnas)) . Recurrimos a la mitad del número de columnas. En cada llamada recursiva, buscamos linealmente el máximo en la columna central actual.
Espacio auxiliar: O (columnas/2) para pila de llamadas recursivas 

Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.