Dada una array de enteros de tamaño n, encuentre el máximo de los mínimos de cada tamaño de ventana en la array. Tenga en cuenta que el tamaño de la ventana varía de 1 a n.
Ejemplo:
Entrada: arr[] = {10, 20, 30, 50, 10, 70, 30}
Salida: 70, 30, 20, 10, 10, 10, 10
El primer elemento en la salida indica el máximo de los mínimos de todas las
ventanas de tamaño 1.
Los mínimos de ventanas de tamaño 1 son {10}, {20}, {30}, {50}, {10},
{70} y {30}. El máximo de estos mínimos es 70
El segundo elemento en la salida indica el máximo de mínimos de todas las
ventanas de tamaño 2. Los mínimos de
ventanas de tamaño 2 son {10}, {20}, {30}, {10}, {10} y
{30}. El máximo de estos mínimos es 30.
El tercer elemento en la salida indica el máximo de mínimos de todas las
ventanas de tamaño 3. Los mínimos de
ventanas de tamaño 3 son {10}, {20}, {10}, {10} y {10} .
El máximo de estos mínimos es 20
De manera similar, se calculan otros elementos de la salida.
Solución ingenua : fuerza bruta.
Enfoque: un enfoque simple de fuerza bruta para resolver este problema puede ser generar todas las ventanas posibles de una longitud particular, digamos ‘L’ y encontrar el elemento mínimo en todas esas ventanas. Luego encuentre el máximo de todos esos elementos y guárdelo. Ahora la longitud de la ventana es 1<=L<=N. Así que tenemos que generar todas las ventanas posibles de tamaño ‘1’ a ‘N’ y para generar cada una de esas ventanas tenemos que marcar los puntos finales de esa ventana. Entonces, para eso, tenemos que usar un bucle anidado para fijar el punto inicial y final de la ventana, respectivamente. Por lo tanto, habrá un uso de bucle anidado triple en el enfoque de fuerza bruta principalmente para fijar la longitud de la ventana, el punto de inicio y el punto final.
C++
// A naive method to find maximum of
// minimum of all windows of different
// sizes
#include <bits/stdc++.h>
using namespace std;
void printMaxOfMin(int arr[], int n)
{
// Consider all windows of different
// sizes starting from size 1
for (int k = 1; k <= n; k++) {
// Initialize max of min for
// current window size k
int maxOfMin = INT_MIN;
// Traverse through all windows
// of current size k
for (int i = 0; i <= n - k; i++) {
// Find minimum of current window
int min = arr[i];
for (int j = 1; j < k; j++) {
if (arr[i + j] < min)
min = arr[i + j];
}
// Update maxOfMin if required
if (min > maxOfMin)
maxOfMin = min;
}
// Print max of min for current
// window size
cout << maxOfMin << " ";
}
}
// Driver program
int main()
{
int arr[] = { 10, 20, 30, 50, 10, 70, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
printMaxOfMin(arr, n);
return 0;
}
Java
// A naive method to find maximum of
// minimum of all windows of different sizes
class Test {
static int arr[] = { 10, 20, 30, 50, 10, 70, 30 };
static void printMaxOfMin(int n)
{
// Consider all windows of different
// sizes starting from size 1
for (int k = 1; k <= n; k++) {
// Initialize max of min for current
// window size k
int maxOfMin = Integer.MIN_VALUE;
// Traverse through all windows of
// current size k
for (int i = 0; i <= n - k; i++) {
// Find minimum of current window
int min = arr[i];
for (int j = 1; j < k; j++) {
if (arr[i + j] < min)
min = arr[i + j];
}
// Update maxOfMin if required
if (min > maxOfMin)
maxOfMin = min;
}
// Print max of min for current
// window size
System.out.print(maxOfMin + " ");
}
}
// Driver method
public static void main(String[] args)
{
printMaxOfMin(arr.length);
}
}
Python3
# A naive method to find maximum of # minimum of all windows of different sizes INT_MIN = -1000000 def printMaxOfMin(arr, n): # Consider all windows of different # sizes starting from size 1 for k in range(1, n + 1): # Initialize max of min for # current window size k maxOfMin = INT_MIN; # Traverse through all windows # of current size k for i in range(n - k + 1): # Find minimum of current window min = arr[i] for j in range(k): if (arr[i + j] < min): min = arr[i + j] # Update maxOfMin if required if (min > maxOfMin): maxOfMin = min # Print max of min for current window size print(maxOfMin, end = " ") # Driver Code arr = [10, 20, 30, 50, 10, 70, 30] n = len(arr) printMaxOfMin(arr, n) # This code is contributed by sahilshelangia
C#
// C# program using Naive approach to find
// maximum of minimum of all windows of
// different sizes
using System;
class GFG{
static int []arr = {10, 20, 30, 50, 10, 70, 30};
// Function to print maximum of minimum
static void printMaxOfMin(int n)
{
// Consider all windows of different
// sizes starting from size 1
for (int k = 1; k <= n; k++)
{
// Initialize max of min for
// current window size k
int maxOfMin = int.MinValue;
// Traverse through all windows
// of current size k
for (int i = 0; i <= n - k; i++)
{
// Find minimum of current window
int min = arr[i];
for (int j = 1; j < k; j++)
{
if (arr[i + j] < min)
min = arr[i + j];
}
// Update maxOfMin if required
if (min > maxOfMin)
maxOfMin = min;
}
// Print max of min for current window size
Console.Write(maxOfMin + " ");
}
}
// Driver Code
public static void Main()
{
printMaxOfMin(arr.Length);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to find maximum of
// minimum of all windows of
// different sizes
// Method to find maximum of
// minimum of all windows of
// different sizes
function printMaxOfMin($arr, $n)
{
// Consider all windows of
// different sizes starting
// from size 1
for($k = 1; $k <= $n; $k++)
{
// Initialize max of min for
// current window size k
$maxOfMin = PHP_INT_MIN;
// Traverse through all windows
// of current size k
for ($i = 0; $i <= $n-$k; $i++)
{
// Find minimum of current window
$min = $arr[$i];
for ($j = 1; $j < $k; $j++)
{
if ($arr[$i + $j] < $min)
$min = $arr[$i + $j];
}
// Update maxOfMin
// if required
if ($min > $maxOfMin)
$maxOfMin = $min;
}
// Print max of min for
// current window size
echo $maxOfMin , " ";
}
}
// Driver Code
$arr= array(10, 20, 30, 50, 10, 70, 30);
$n = sizeof($arr);
printMaxOfMin($arr, $n);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// A naive method to find maximum of
// minimum of all windows of different sizes
var arr = [ 10, 20, 30, 50, 10, 70, 30 ];
function printMaxOfMin(n) {
// Consider all windows of different
// sizes starting from size 1
for (k = 1; k <= n; k++) {
// Initialize max of min for current
// window size k
var maxOfMin = Number.MIN_VALUE;
// Traverse through all windows of
// current size k
for (i = 0; i <= n - k; i++) {
// Find minimum of current window
var min = arr[i];
for (j = 1; j < k; j++) {
if (arr[i + j] < min)
min = arr[i + j];
}
// Update maxOfMin if required
if (min > maxOfMin)
maxOfMin = min;
}
// Print max of min for current
// window size
document.write(maxOfMin + " ");
}
}
// Driver method
printMaxOfMin(arr.length);
// This code contributed by aashish1995
</script>
Producción
70 30 20 10 10 10 10
Análisis de Complejidad:
- Complejidad Temporal: O(n 3 ).
Como hay un uso de bucle anidado triple en este enfoque. - Espacio auxiliar: O(1)
Dado que no se ha utilizado ninguna estructura de datos adicional para almacenar los valores.
Solución eficiente :
Podemos resolver este problema en tiempo O(n). La idea es utilizar espacio extra. A continuación se detallan los pasos.
Paso 1:
- Encuentre índices del siguiente menor y el anterior menor para cada elemento. El siguiente más pequeño es el elemento más pequeño más cercano en el lado derecho de arr[i]. De manera similar, un elemento más pequeño anterior es el elemento más pequeño más cercano en el lado izquierdo de arr[i].
- Si no hay ningún elemento más pequeño en el lado derecho, entonces el siguiente más pequeño es n. Si no hay menor en el lado izquierdo, entonces el menor anterior es -1.
- Para la entrada {10, 20, 30, 50, 10, 70, 30}, la array de índices del siguiente menor es {7, 4, 4, 4, 7, 6, 7}.
- Para la entrada {10, 20, 30, 50, 10, 70, 30}, la array de índices de menor anterior es {-1, 0, 1, 2, -1, 4, 4}
- Este paso se puede realizar en tiempo O(n) usando el enfoque discutido en el siguiente elemento mayor .
Paso 2:
Una vez que tenemos índices de siguiente y anterior más pequeños, sabemos que arr[i] es un mínimo de una ventana de longitud “derecha[i] – izquierda[i] – 1”. Las longitudes de las ventanas para las que los elementos son mínimos son {7, 3, 2, 1, 7, 1, 2}. Esta array indica que el primer elemento es mínimo en la ventana de tamaño 7, el segundo elemento es mínimo en la ventana de tamaño 3, y así sucesivamente.
Cree una array auxiliar ans[n+1] para almacenar el resultado. Los valores en ans[] se pueden completar iterando a través de right[] y left[]
for (int i=0; i < n; i++)
{
// length of the interval
int len = right[i] - left[i] - 1;
// arr[i] is a possible answer for
// this length len interval
ans[len] = max(ans[len], arr[i]);
}
Obtenemos la array ans[] como {0, 70, 30, 20, 0, 0, 0, 10}. Tenga en cuenta que ans[0] o respuesta para la longitud 0 es inútil.
Paso 3:
Algunas entradas en ans[] son 0 y aún no se han completado. Por ejemplo, sabemos que el máximo del mínimo para las longitudes 1, 2, 3 y 7 son 70, 30, 20 y 10 respectivamente, pero no sabemos lo mismo para las longitudes 4, 5 y 6.
A continuación se presentan algunas observaciones importantes para completar las entradas restantes
- El resultado para la longitud i, es decir, ans[i] siempre sería mayor o igual que el resultado para la longitud i+1, es decir, ans[i+1].
- Si ans[i] no está lleno, significa que no hay ningún elemento directo que sea mínimo de longitud i y, por lo tanto, el elemento de longitud ans[i+1], o ans[i+2], y así sucesivamente es lo mismo que ans [i]
Así que llenamos el resto de las entradas usando el siguiente bucle.
for (int i=n-1; i>=1; i--)
ans[i] = max(ans[i], ans[i+1]);
A continuación se muestra la implementación del algoritmo anterior.
C++
// An efficient C++ program to find
// maximum of all minimums of
// windows of different sizes
#include <iostream>
#include<stack>
using namespace std;
void printMaxOfMin(int arr[], int n)
{
// Used to find previous and next smaller
stack<int> s;
// Arrays to store previous and next smaller
int left[n+1];
int right[n+1];
// Initialize elements of left[] and right[]
for (int i=0; i<n; i++)
{
left[i] = -1;
right[i] = n;
}
// Fill elements of left[] using logic discussed on
// https://www.geeksforgeeks.org/next-greater-element/
for (int i=0; i<n; i++)
{
while (!s.empty() && arr[s.top()] >= arr[i])
s.pop();
if (!s.empty())
left[i] = s.top();
s.push(i);
}
// Empty the stack as stack is
// going to be used for right[]
while (!s.empty())
s.pop();
// Fill elements of right[] using same logic
for (int i = n-1 ; i>=0 ; i-- )
{
while (!s.empty() && arr[s.top()] >= arr[i])
s.pop();
if(!s.empty())
right[i] = s.top();
s.push(i);
}
// Create and initialize answer array
int ans[n+1];
for (int i=0; i<=n; i++)
ans[i] = 0;
// Fill answer array by comparing minimums of all
// lengths computed using left[] and right[]
for (int i=0; i<n; i++)
{
// length of the interval
int len = right[i] - left[i] - 1;
// arr[i] is a possible answer for this length
// 'len' interval, check if arr[i] is more than
// max for 'len'
ans[len] = max(ans[len], arr[i]);
}
// Some entries in ans[] may not be filled yet. Fill
// them by taking values from right side of ans[]
for (int i=n-1; i>=1; i--)
ans[i] = max(ans[i], ans[i+1]);
// Print the result
for (int i=1; i<=n; i++)
cout << ans[i] << " ";
}
// Driver program
int main()
{
int arr[] = {10, 20, 30, 50, 10, 70, 30};
int n = sizeof(arr)/sizeof(arr[0]);
printMaxOfMin(arr, n);
return 0;
}
Java
// An efficient Java program to find
// maximum of all minimums of
// windows of different size
import java.util.Stack;
class Test
{
static int arr[] = {10, 20, 30, 50, 10, 70, 30};
static void printMaxOfMin(int n)
{
// Used to find previous and next smaller
Stack<Integer> s = new Stack<>();
// Arrays to store previous and next smaller
int left[] = new int[n+1];
int right[] = new int[n+1];
// Initialize elements of left[] and right[]
for (int i=0; i<n; i++)
{
left[i] = -1;
right[i] = n;
}
// Fill elements of left[] using logic discussed on
// https://www.geeksforgeeks.org/next-greater-element/
for (int i=0; i<n; i++)
{
while (!s.empty() && arr[s.peek()] >= arr[i])
s.pop();
if (!s.empty())
left[i] = s.peek();
s.push(i);
}
// Empty the stack as stack is
// going to be used for right[]
while (!s.empty())
s.pop();
// Fill elements of right[] using same logic
for (int i = n-1 ; i>=0 ; i-- )
{
while (!s.empty() && arr[s.peek()] >= arr[i])
s.pop();
if(!s.empty())
right[i] = s.peek();
s.push(i);
}
// Create and initialize answer array
int ans[] = new int[n+1];
for (int i=0; i<=n; i++)
ans[i] = 0;
// Fill answer array by comparing minimums of all
// lengths computed using left[] and right[]
for (int i=0; i<n; i++)
{
// length of the interval
int len = right[i] - left[i] - 1;
// arr[i] is a possible answer for this length
// 'len' interval, check if arr[i] is more than
// max for 'len'
ans[len] = Math.max(ans[len], arr[i]);
}
// Some entries in ans[] may not be filled yet. Fill
// them by taking values from right side of ans[]
for (int i=n-1; i>=1; i--)
ans[i] = Math.max(ans[i], ans[i+1]);
// Print the result
for (int i=1; i<=n; i++)
System.out.print(ans[i] + " ");
}
// Driver method
public static void main(String[] args)
{
printMaxOfMin(arr.length);
}
}
Python3
# An efficient Python3 program to find # maximum of all minimums of windows of # different sizes def printMaxOfMin(arr, n): s = [] # Used to find previous # and next smaller # Arrays to store previous and next # smaller. Initialize elements of # left[] and right[] left = [-1] * (n + 1) right = [n] * (n + 1) # Fill elements of left[] using logic discussed on # https:#www.geeksforgeeks.org/next-greater-element for i in range(n): while (len(s) != 0 and arr[s[-1]] >= arr[i]): s.pop() if (len(s) != 0): left[i] = s[-1] s.append(i) # Empty the stack as stack is going # to be used for right[] while (len(s) != 0): s.pop() # Fill elements of right[] using same logic for i in range(n - 1, -1, -1): while (len(s) != 0 and arr[s[-1]] >= arr[i]): s.pop() if(len(s) != 0): right[i] = s[-1] s.append(i) # Create and initialize answer array ans = [0] * (n + 1) for i in range(n + 1): ans[i] = 0 # Fill answer array by comparing minimums # of all. Lengths computed using left[] # and right[] for i in range(n): # Length of the interval Len = right[i] - left[i] - 1 # arr[i] is a possible answer for this # Length 'Len' interval, check if arr[i] # is more than max for 'Len' ans[Len] = max(ans[Len], arr[i]) # Some entries in ans[] may not be filled # yet. Fill them by taking values from # right side of ans[] for i in range(n - 1, 0, -1): ans[i] = max(ans[i], ans[i + 1]) # Print the result for i in range(1, n + 1): print(ans[i], end = " ") # Driver Code if __name__ == '__main__': arr = [10, 20, 30, 50, 10, 70, 30] n = len(arr) printMaxOfMin(arr, n) # This code is contributed by PranchalK
C#
// An efficient C# program to find maximum
// of all minimums of windows of different size
using System;
using System.Collections.Generic;
class GFG
{
public static int[] arr = new int[] {10, 20, 30, 50,
10, 70, 30};
public static void printMaxOfMin(int n)
{
// Used to find previous and next smaller
Stack<int> s = new Stack<int>();
// Arrays to store previous
// and next smaller
int[] left = new int[n + 1];
int[] right = new int[n + 1];
// Initialize elements of left[]
// and right[]
for (int i = 0; i < n; i++)
{
left[i] = -1;
right[i] = n;
}
// Fill elements of left[] using logic discussed on
// https://www.geeksforgeeks.org/next-greater-element/
for (int i = 0; i < n; i++)
{
while (s.Count > 0 &&
arr[s.Peek()] >= arr[i])
{
s.Pop();
}
if (s.Count > 0)
{
left[i] = s.Peek();
}
s.Push(i);
}
// Empty the stack as stack is going
// to be used for right[]
while (s.Count > 0)
{
s.Pop();
}
// Fill elements of right[] using
// same logic
for (int i = n - 1 ; i >= 0 ; i--)
{
while (s.Count > 0 &&
arr[s.Peek()] >= arr[i])
{
s.Pop();
}
if (s.Count > 0)
{
right[i] = s.Peek();
}
s.Push(i);
}
// Create and initialize answer array
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++)
{
ans[i] = 0;
}
// Fill answer array by comparing
// minimums of all lengths computed
// using left[] and right[]
for (int i = 0; i < n; i++)
{
// length of the interval
int len = right[i] - left[i] - 1;
// arr[i] is a possible answer for
// this length 'len' interval, check x
// if arr[i] is more than max for 'len'
ans[len] = Math.Max(ans[len], arr[i]);
}
// Some entries in ans[] may not be
// filled yet. Fill them by taking
// values from right side of ans[]
for (int i = n - 1; i >= 1; i--)
{
ans[i] = Math.Max(ans[i], ans[i + 1]);
}
// Print the result
for (int i = 1; i <= n; i++)
{
Console.Write(ans[i] + " ");
}
}
// Driver Code
public static void Main(string[] args)
{
printMaxOfMin(arr.Length);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// An efficient Javascript program to find maximum
// of all minimums of windows of different size
let arr = [10, 20, 30, 50, 10, 70, 30];
function printMaxOfMin(n)
{
// Used to find previous and next smaller
let s = [];
// Arrays to store previous
// and next smaller
let left = new Array(n + 1);
left.fill(0);
let right = new Array(n + 1);
right.fill(0);
// Initialize elements of left[]
// and right[]
for (let i = 0; i < n; i++)
{
left[i] = -1;
right[i] = n;
}
// Fill elements of left[] using logic discussed on
// https://www.geeksforgeeks.org/next-greater-element/
for (let i = 0; i < n; i++)
{
while (s.length > 0 && arr[s[s.length - 1]] >= arr[i])
{
s.pop();
}
if (s.length > 0)
{
left[i] = s[s.length - 1];
}
s.push(i);
}
// Empty the stack as stack is going
// to be used for right[]
while (s.length > 0)
{
s.pop();
}
// Fill elements of right[] using
// same logic
for (let i = n - 1 ; i >= 0 ; i--)
{
while (s.length > 0 && arr[s[s.length - 1]] >= arr[i])
{
s.pop();
}
if (s.length > 0)
{
right[i] = s[s.length - 1];
}
s.push(i);
}
// Create and initialize answer array
let ans = new Array(n + 1);
ans.fill(0);
for (let i = 0; i <= n; i++)
{
ans[i] = 0;
}
// Fill answer array by comparing
// minimums of all lengths computed
// using left[] and right[]
for (let i = 0; i < n; i++)
{
// length of the interval
let len = right[i] - left[i] - 1;
// arr[i] is a possible answer for
// this length 'len' interval, check x
// if arr[i] is more than max for 'len'
ans[len] = Math.max(ans[len], arr[i]);
}
// Some entries in ans[] may not be
// filled yet. Fill them by taking
// values from right side of ans[]
for (let i = n - 1; i >= 1; i--)
{
ans[i] = Math.max(ans[i], ans[i + 1]);
}
// Print the result
for (let i = 1; i <= n; i++)
{
document.write(ans[i] + " ");
}
}
printMaxOfMin(arr.length);
// This code is contributed by decode2207.
</script>
Producción
70 30 20 10 10 10 10
Análisis de Complejidad:
- Complejidad temporal: O(n).
Cada subtarea en este enfoque requiere tiempo lineal. - Espacio Auxiliar : O(n).
Uso de la pila para calcular el siguiente mínimo y arrays para almacenar los resultados intermedios.
Este artículo es una contribución de Ekta Goel y Ayush Govil . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA