Encuentre el máximo de los mínimos de las capas de Matrix usando los números 1 a N ^ 2

Dada una array cuadrada de tamaño N*N usando los números 1 a N^2 , la tarea es encontrar el máximo de los mínimos de cada capa de la array.

Las capas de la array son los elementos de contorno de la subarray que comienzan en (i, i) y terminan en (N – i + 1, N – i + 1), donde 1<= i<= ceil(N/2 ).

Ejemplos:

 Entrada: A continuación se muestra la array dada:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Salida: 6
Explicación: Las capas son {1, 2, 3, 4, 8, 12, 16, 15, 14 , 13, 9, 5} con mínimo 1 y {6, 7, 10, 11} con mínimo 6. El máximo de 1 y 6 es 6.

Entrada: A continuación se muestra la array dada: 
1 2 3
4 30 5
1 2 3
Salida: 30
Explicación: Las capas son {1, 2, 3, 5, 3, 2, 1, 4, 1} con un mínimo de 1 y {30 } con un mínimo de 30. El máximo de 1 y 30 es 30.

Enfoque: La idea es observar cuidadosamente, para la i ^-ésima capa, los elementos del límite superior, izquierdo, derecho e inferior están en índices:

• el límite superior está en los índices (i, j)
• el límite izquierdo está en los índices (j, i)
• el límite derecho está en los índices (j, n – i + 1)
• el límite inferior está en los índices (n – i + 1, j), donde i <= j <= n – i + 1

Por lo tanto, encuentre los mínimos de cada capa y almacene el máximo de estos mínimos.

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

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// of the boundary elements
int getBoundaryMin(int a[][4], int n,
                   int index)
{
    int min1 = INT_MAX;
 
    for(int i = index; i < n - index; i++)
    {
         
        // Top boundary
        min1 = min(min1,
                   a[index][i]);
 
        // Left boundary
        min1 = min(min1,
                   a[i][index]);
 
        // Right boundary
        min1 = min(min1,
                    a[i][n - index - 1]);
 
        // Bottom boundary
        min1 = min(min1,
                   a[n - index - 1][i]);
    }
    return min1;
}
 
// Function to find the maximum of
// minimums of all layers
void MaximumOfMinimum(int a[][4], int n)
{
     
    // Calculate the layers
    int layers = n / 2 + n % 2;
    int max1 = INT_MIN;
 
    // Iterate for all the layers
    for(int i = 0; i < layers; i++)
    {
         
        // Find maximum
        max1 = max(max1,
                   getBoundaryMin(a, n, i));
    }
     
    // Print the answer
    cout << (max1);
}
 
// Driver Code
int main()
{
     
    // Initialize the matrix
    int a[][4] = { { 1, 2, 3, 4 },
                   { 5, 6, 7, 8 },
                   { 9, 10, 11, 12 },
                   { 13, 14, 15, 16 } };
 
    int n = sizeof(a) / sizeof(a[0]);
 
    // Function call
    MaximumOfMinimum(a, n);
}
 
// This code is contributed by chitranayal

// Java Program for the above approach
 
class GFG {
 
    // Function to return the minimum
    // of the boundary elements
    static int
    getBoundaryMin(int a[][], int n,
                   int index)
    {
        int min = Integer.MAX_VALUE;
 
        for (int i = index; i < n - index; i++) {
 
            // Top boundary
            min = Math.min(
                min,
                a[index][i]);
 
            // Left boundary
            min = Math.min(
                min,
                a[i][index]);
 
            // Right boundary
            min = Math.min(
                min,
                a[i][n - index - 1]);
 
            // Bottom boundary
            min = Math.min(
                min,
                a[n - index - 1][i]);
        }
 
        return min;
    }
 
    // Function to find the maximum of
    // minimums of all layers
    static void MaximumOfMinimum(
        int a[][], int n)
    {
        // Calculate the layers
        int layers = n / 2 + n % 2;
        int max = Integer.MIN_VALUE;
 
        // Iterate for all the layers
        for (int i = 0; i < layers; i++) {
 
            // Find maximum
            max
                = Math.max(
                    max,
                    getBoundaryMin(a, n, i));
        }
 
        // Print the answer
        System.out.print(max);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Initialize the matrix
        int a[][] = { { 1, 2, 3, 4 },
                      { 5, 6, 7, 8 },
                      { 9, 10, 11, 12 },
                      { 13, 14, 15, 16 } };
 
        int n = a.length;
 
        // Function call
        MaximumOfMinimum(a, n);
    }
}

# Python3 program for the above approach
import sys
 
# Function to return the minimum
# of the boundary elements
def getBoundaryMin(a, n, index):
     
    min1 = sys.maxsize
 
    for i in range(index, n - index):
         
        # Top boundary
        min1 = min(min1, a[index][i])
 
        # Left boundary
        min1 = min(min1, a[i][index])
 
        # Right boundary
        min1 = min(min1, a[i][n - index - 1])
 
        # Bottom boundary
        min1 = min(min1, a[n - index - 1][i])
     
    return min1
 
# Function to find the maximum of
# minimums of all layers
def MaximumOfMinimum(a, n):
     
    # Calculate the layers
    layers = n // 2 + n % 2
    max1 = -sys.maxsize - 1
 
    # Iterate for all the layers
    for i in range(0, layers):
         
        # Find maximum
        max1 = max(max1, getBoundaryMin(a, n, i))
     
    # Print the answer
    print(max1)
 
# Driver Code
     
# Initialize the matrix
a = [ [ 1, 2, 3, 4 ],
      [ 5, 6, 7, 8 ],
      [ 9, 10, 11, 12 ] ,
      [ 13, 14, 15, 16 ] ]
 
n = len(a)
 
# Function call
MaximumOfMinimum(a, n)
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
 
class GFG{
 
// Function to return the minimum
// of the boundary elements
static int getBoundaryMin(int[,]a, int n,
                          int index)
{
    int min = int.MaxValue;
 
    for(int i = index; i < n - index; i++)
    {
         
        // Top boundary
        min = Math.Min(min, a[index, i]);
 
        // Left boundary
        min = Math.Min(min, a[i, index]);
 
        // Right boundary
        min = Math.Min(min, a[i, n - index - 1]);
 
        // Bottom boundary
        min = Math.Min(min, a[n - index - 1, i]);
    }
    return min;
}
 
// Function to find the maximum of
// minimums of all layers
static void MaximumOfMinimum(int[,]a, int n)
{
     
    // Calculate the layers
    int layers = n / 2 + n % 2;
    int max = int.MinValue;
 
    // Iterate for all the layers
    for(int i = 0; i < layers; i++)
    {
         
        // Find maximum
        max = Math.Max(max,
                       getBoundaryMin(a, n, i));
    }
 
    // Print the answer
    Console.Write(max);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Initialize the matrix
    int[,]a = { { 1, 2, 3, 4 },
                { 5, 6, 7, 8 },
                { 9, 10, 11, 12 },
                { 13, 14, 15, 16 } };
 
    int n = a.GetLength(0);
 
    // Function call
    MaximumOfMinimum(a, n);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program for the above approach
 
// Function to return the minimum
// of the boundary elements
function getBoundaryMin(a, n, index)
{
    min1 = 1000000000;
     
    for(var i = index; i < n - index; i++)
    {
         
        // Top boundary
        min1 = Math.min(min1,
        a[index][i]);
         
        // Left boundary
        min1 = Math.min(min1,
        a[i][index]);
         
        // Right boundary
        min1 = Math.min(min1,
        a[i][n - index - 1]);
         
        // Bottom boundary
        min1 = Math.min(min1,
        a[n - index - 1][i]);
    }
    return min1;
}
     
// Function to find the maximum of
// minimums of all layers
function MaximumOfMinimum(a, n)
{
     
    // Calculate the layers
    var layers = parseInt(n / 2) + n % 2;
    var max1 = -1000000000;
     
    // Iterate for all the layers
    for(var i = 0; i < layers; i++)
    {
         
        // Find maximum
        max1 = Math.max(max1,
        getBoundaryMin(a, n, i));
    }
     
    // Print the answer
    document.write(max1);
}
 
// Driver Code
 
// Initialize the matrix
var a = [ [ 1, 2, 3, 4 ],
          [ 5, 6, 7, 8 ],
          [ 9, 10, 11, 12 ],
          [ 13, 14, 15, 16 ] ];
var n = a.length;
 
// Function call
MaximumOfMinimum(a, n);
 
// This code is contributed by itsok
 
</script>

6

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)