Dada una array arr[] de tamaño N y entero Y , la tarea es encontrar un mínimo de todas las diferencias entre los elementos máximo y mínimo en todas las subarreglas de tamaño Y .
Ejemplos:
Entrada: arr[] = { 3, 2, 4, 5, 6, 1, 9 } Y = 3
Salida: 2
Explicación:
Todos los subarreglos de longitud = 3 son:
{3, 2, 4} donde elemento máximo = 4 y elemento mínimo = 2 diferencia = 2
{2, 4, 5} donde elemento máximo = 5 y elemento mínimo = 2 diferencia = 3
{4, 5, 6} donde elemento máximo = 6 y elemento mínimo = 4 diferencia = 2
{5, 6, 1} donde elemento máximo = 6 y elemento mínimo = 1 diferencia = 5
{6, 1, 9} donde elemento máximo = 9 y elemento mínimo = 6 diferencia = 3
De estos, el mínimo es 2.
Entrada: arr[] = { 1, 2, 3, 3, 2, 2 } Y = 4
Salida: 1
Explicación:
Todos los subarreglos de longitud = 4 son:
{1, 2, 3, 3} elemento máximo = 3 y mínimo elemento = 1 diferencia = 2
{2, 3, 3, 2} elemento máximo = 3 y elemento mínimo = 2 diferencia = 1
{3, 3, 2, 2} elemento máximo = 3 y elemento mínimo = 2 diferencia = 1
Fuera de estos, el mínimo es 1.
Enfoque ingenuo: la idea ingenua es atravesar para cada índice i en el rango [0, N – Y] usar otro ciclo para atravesar desde el i -ésimo índice hasta (i + Y – 1) el ésimo índice y luego calcular los elementos mínimo y máximo en un subarreglo de tamaño Y y, por lo tanto, calcule la diferencia del elemento máximo y mínimo para esa i -ésima iteración. Finalmente, controlando las diferencias, evalúe la diferencia mínima.
Complejidad temporal: O(N*Y)
Espacio auxiliar: O(1)
Enfoque Eficiente: La idea es utilizar el concepto del enfoque discutido en el artículo El Siguiente Elemento Mayor . A continuación se muestran los pasos:
- Cree dos arrays maxarr[] y minarr[] , donde maxarr[] almacenará el índice del elemento que es el siguiente mayor al elemento en el i -ésimo índice y minarr[] almacenará el índice del siguiente elemento que es menor que el elemento en el i -ésimo índice .
- Inicialice una pila con 0 para almacenar los índices en los dos casos anteriores.
- Para cada índice, i en el rango [0, N – Y] , utilizando un bucle anidado y un enfoque de ventana deslizante, forman dos arrays submax y submin. Estos arreglos almacenarán elementos máximos y mínimos en el subarreglo en la i -ésima iteración.
- Finalmente, calcule la diferencia mínima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the maximum of all
// the subarrays of size Y
vector<int> get_submaxarr(int* arr,
int n, int y)
{
int j = 0;
stack<int> stk;
// ith index of maxarr array
// will be the index upto which
// Arr[i] is maximum
vector<int> maxarr(n);
stk.push(0);
for (int i = 1; i < n; i++) {
// Stack is used to find the
// next larger element and
// keeps track of index of
// current iteration
while (stk.empty() == false
and arr[i] > arr[stk.top()]) {
maxarr[stk.top()] = i - 1;
stk.pop();
}
stk.push(i);
}
// Loop for remaining indexes
while (!stk.empty()) {
maxarr[stk.top()] = n - 1;
stk.pop();
}
vector<int> submax;
for (int i = 0; i <= n - y; i++) {
// j < i used to keep track
// whether jth element is
// inside or outside the window
while (maxarr[j] < i + y - 1
or j < i) {
j++;
}
submax.push_back(arr[j]);
}
// Return submax
return submax;
}
// Function to get the minimum for
// all subarrays of size Y
vector<int> get_subminarr(int* arr,
int n, int y)
{
int j = 0;
stack<int> stk;
// ith index of minarr array
// will be the index upto which
// Arr[i] is minimum
vector<int> minarr(n);
stk.push(0);
for (int i = 1; i < n; i++) {
// Stack is used to find the
// next smaller element and
// keeping track of index of
// current iteration
while (stk.empty() == false
and arr[i] < arr[stk.top()]) {
minarr[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
// Loop for remaining indexes
while (!stk.empty()) {
minarr[stk.top()] = n;
stk.pop();
}
vector<int> submin;
for (int i = 0; i <= n - y; i++) {
// j < i used to keep track
// whether jth element is inside
// or outside the window
while (minarr[j] <= i + y - 1
or j < i) {
j++;
}
submin.push_back(arr[j]);
}
// Return submin
return submin;
}
// Function to get minimum difference
void getMinDifference(int Arr[], int N,
int Y)
{
// Create submin and submax arrays
vector<int> submin
= get_subminarr(Arr, N, Y);
vector<int> submax
= get_submaxarr(Arr, N, Y);
// Store initial difference
int minn = submax[0] - submin[0];
int b = submax.size();
for (int i = 1; i < b; i++) {
// Calculate temporary difference
int dif = submax[i] - submin[i];
minn = min(minn, dif);
}
// Final minimum difference
cout << minn << "\n";
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3, 3, 2, 2 };
int N = sizeof arr / sizeof arr[0];
// Given subarray size
int Y = 4;
// Function Call
getMinDifference(arr, N, Y);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to get the maximum of all
// the subarrays of size Y
static Vector<Integer> get_submaxarr(int[] arr, int n,
int y)
{
int j = 0;
Stack<Integer> stk = new Stack<Integer>();
// ith index of maxarr array
// will be the index upto which
// Arr[i] is maximum
int[] maxarr = new int[n];
Arrays.fill(maxarr,0);
stk.push(0);
for(int i = 1; i < n; i++)
{
// Stack is used to find the
// next larger element and
// keeps track of index of
// current iteration
while (stk.size() != 0 &&
arr[i] > arr[stk.peek()])
{
maxarr[stk.peek()] = i - 1;
stk.pop();
}
stk.push(i);
}
// Loop for remaining indexes
while (stk.size() != 0)
{
maxarr[stk.size()] = n - 1;
stk.pop();
}
Vector<Integer> submax = new Vector<Integer>();
for(int i = 0; i <= n - y; i++)
{
// j < i used to keep track
// whether jth element is
// inside or outside the window
while (maxarr[j] < i + y - 1 || j < i)
{
j++;
}
submax.add(arr[j]);
}
// Return submax
return submax;
}
// Function to get the minimum for
// all subarrays of size Y
static Vector<Integer> get_subminarr(int[] arr, int n,
int y)
{
int j = 0;
Stack<Integer> stk = new Stack<Integer>();
// ith index of minarr array
// will be the index upto which
// Arr[i] is minimum
int[] minarr = new int[n];
Arrays.fill(minarr,0);
stk.push(0);
for(int i = 1; i < n; i++)
{
// Stack is used to find the
// next smaller element and
// keeping track of index of
// current iteration
while (stk.size() != 0 &&
arr[i] < arr[stk.peek()])
{
minarr[stk.peek()] = i;
stk.pop();
}
stk.push(i);
}
// Loop for remaining indexes
while (stk.size() != 0)
{
minarr[stk.peek()] = n;
stk.pop();
}
Vector<Integer> submin = new Vector<Integer>();
for(int i = 0; i <= n - y; i++)
{
// j < i used to keep track
// whether jth element is inside
// or outside the window
while (minarr[j] <= i + y - 1 || j < i)
{
j++;
}
submin.add(arr[j]);
}
// Return submin
return submin;
}
// Function to get minimum difference
static void getMinDifference(int[] Arr, int N, int Y)
{
// Create submin and submax arrays
Vector<Integer> submin = get_subminarr(Arr, N, Y);
Vector<Integer> submax = get_submaxarr(Arr, N, Y);
// Store initial difference
int minn = submax.get(0) - submin.get(0);
int b = submax.size();
for(int i = 1; i < b; i++)
{
// Calculate temporary difference
int dif = submax.get(i) - submin.get(i) + 1;
minn = Math.min(minn, dif);
}
// Final minimum difference
System.out.print(minn);
}
// Driver code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 1, 2, 3, 3, 2, 2 };
int N = arr.length;
// Given subarray size
int Y = 4;
// Function Call
getMinDifference(arr, N, Y);
}
}
// This code is contributed by decode2207
Python3
# Python3 program for the above approach # Function to get the maximum of all # the subarrays of size Y def get_submaxarr(arr, n, y): j = 0 stk = [] # ith index of maxarr array # will be the index upto which # Arr[i] is maximum maxarr = [0] * n stk.append(0) for i in range(1, n): # Stack is used to find the # next larger element and # keeps track of index of # current iteration while (len(stk) > 0 and arr[i] > arr[stk[-1]]): maxarr[stk[-1]] = i - 1 stk.pop() stk.append(i) # Loop for remaining indexes while (stk): maxarr[stk[-1]] = n - 1 stk.pop() submax = [] for i in range(n - y + 1): # j < i used to keep track # whether jth element is # inside or outside the window while (maxarr[j] < i + y - 1 or j < i): j += 1 submax.append(arr[j]) # Return submax return submax # Function to get the minimum for # all subarrays of size Y def get_subminarr(arr, n, y): j = 0 stk = [] # ith index of minarr array # will be the index upto which # Arr[i] is minimum minarr = [0] * n stk.append(0) for i in range(1 , n): # Stack is used to find the # next smaller element and # keeping track of index of # current iteration while (stk and arr[i] < arr[stk[-1]]): minarr[stk[-1]] = i stk.pop() stk.append(i) # Loop for remaining indexes while (stk): minarr[stk[-1]] = n stk.pop() submin = [] for i in range(n - y + 1): # j < i used to keep track # whether jth element is inside # or outside the window while (minarr[j] <= i + y - 1 or j < i): j += 1 submin.append(arr[j]) # Return submin return submin # Function to get minimum difference def getMinDifference(Arr, N, Y): # Create submin and submax arrays submin = get_subminarr(Arr, N, Y) submax = get_submaxarr(Arr, N, Y) # Store initial difference minn = submax[0] - submin[0] b = len(submax) for i in range(1, b): # Calculate temporary difference diff = submax[i] - submin[i] minn = min(minn, diff) # Final minimum difference print(minn) # Driver code # Given array arr[] arr = [ 1, 2, 3, 3, 2, 2 ] N = len(arr) # Given subarray size Y = 4 # Function call getMinDifference(arr, N, Y) # This code is contributed by Stuti Pathak
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to get the maximum of all
// the subarrays of size Y
static List<int> get_submaxarr(int[] arr, int n, int y)
{
int j = 0;
Stack<int> stk = new Stack<int>();
// ith index of maxarr array
// will be the index upto which
// Arr[i] is maximum
int[] maxarr = new int[n];
Array.Fill(maxarr,0);
stk.Push(0);
for (int i = 1; i < n; i++) {
// Stack is used to find the
// next larger element and
// keeps track of index of
// current iteration
while (stk.Count!=0 && arr[i] > arr[stk.Peek()]) {
maxarr[stk.Peek()] = i - 1;
stk.Pop();
}
stk.Push(i);
}
// Loop for remaining indexes
while (stk.Count!=0) {
maxarr[stk.Count] = n - 1;
stk.Pop();
}
List<int> submax = new List<int>();
for (int i = 0; i <= n - y; i++) {
// j < i used to keep track
// whether jth element is
// inside or outside the window
while (maxarr[j] < i + y - 1
|| j < i) {
j++;
}
submax.Add(arr[j]);
}
// Return submax
return submax;
}
// Function to get the minimum for
// all subarrays of size Y
static List<int> get_subminarr(int[] arr, int n, int y)
{
int j = 0;
Stack<int> stk = new Stack<int>();
// ith index of minarr array
// will be the index upto which
// Arr[i] is minimum
int[] minarr = new int[n];
Array.Fill(minarr,0);
stk.Push(0);
for (int i = 1; i < n; i++) {
// Stack is used to find the
// next smaller element and
// keeping track of index of
// current iteration
while (stk.Count!=0
&& arr[i] < arr[stk.Peek()]) {
minarr[stk.Peek()] = i;
stk.Pop();
}
stk.Push(i);
}
// Loop for remaining indexes
while (stk.Count!=0) {
minarr[stk.Peek()] = n;
stk.Pop();
}
List<int> submin = new List<int>();
for (int i = 0; i <= n - y; i++) {
// j < i used to keep track
// whether jth element is inside
// or outside the window
while (minarr[j] <= i + y - 1
|| j < i) {
j++;
}
submin.Add(arr[j]);
}
// Return submin
return submin;
}
// Function to get minimum difference
static void getMinDifference(int[] Arr, int N, int Y)
{
// Create submin and submax arrays
List<int> submin
= get_subminarr(Arr, N, Y);
List<int> submax
= get_submaxarr(Arr, N, Y);
// Store initial difference
int minn = submax[0] - submin[0];
int b = submax.Count;
for (int i = 1; i < b; i++) {
// Calculate temporary difference
int dif = submax[i] - submin[i] + 1;
minn = Math.Min(minn, dif);
}
// Final minimum difference
Console.WriteLine(minn);
}
static void Main() {
// Given array arr[]
int[] arr = { 1, 2, 3, 3, 2, 2 };
int N = arr.Length;
// Given subarray size
int Y = 4;
// Function Call
getMinDifference(arr, N, Y);
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript program for the above approach
// Function to get the maximum of all
// the subarrays of size Y
function get_submaxarr(arr, n, y)
{
var j = 0;
var stk = [];
// ith index of maxarr array
// will be the index upto which
// Arr[i] is maximum
var maxarr = Array(n);
stk.push(0);
for (var i = 1; i < n; i++) {
// Stack is used to find the
// next larger element and
// keeps track of index of
// current iteration
while (stk.length!=0
&& arr[i] > arr[stk[stk.length-1]]) {
maxarr[stk[stk.length-1]] = i - 1;
stk.pop();
}
stk.push(i);
}
// Loop for remaining indexes
while (stk.length!=0) {
maxarr[stk[stk.length-1]] = n - 1;
stk.pop();
}
var submax = [];
for (var i = 0; i <= n - y; i++) {
// j < i used to keep track
// whether jth element is
// inside or outside the window
while (maxarr[j] < i + y - 1
|| j < i) {
j++;
}
submax.push(arr[j]);
}
// Return submax
return submax;
}
// Function to get the minimum for
// all subarrays of size Y
function get_subminarr(arr, n, y)
{
var j = 0;
var stk = [];
// ith index of minarr array
// will be the index upto which
// Arr[i] is minimum
var minarr = Array(n);
stk.push(0);
for (var i = 1; i < n; i++) {
// Stack is used to find the
// next smaller element and
// keeping track of index of
// current iteration
while (stk.length!=0
&& arr[i] < arr[stk[stk.length-1]]) {
minarr[stk[stk.length-1]] = i;
stk.pop();
}
stk.push(i);
}
// Loop for remaining indexes
while (stk.length!=0) {
minarr[stk[stk.length-1]] = n;
stk.pop();
}
var submin = [];
for (var i = 0; i <= n - y; i++) {
// j < i used to keep track
// whether jth element is inside
// or outside the window
while (minarr[j] <= i + y - 1
|| j < i) {
j++;
}
submin.push(arr[j]);
}
// Return submin
return submin;
}
// Function to get minimum difference
function getMinDifference(Arr, N, Y)
{
// Create submin and submax arrays
var submin
= get_subminarr(Arr, N, Y);
var submax
= get_submaxarr(Arr, N, Y);
// Store initial difference
var minn = submax[0] - submin[0];
var b = submax.length;
for (var i = 1; i < b; i++) {
// Calculate temporary difference
var dif = submax[i] - submin[i];
minn = Math.min(minn, dif);
}
// Final minimum difference
document.write( minn + "<br>");
}
// Driver Code
// Given array arr[]
var arr = [1, 2, 3, 3, 2, 2];
var N = arr.length
// Given subarray size
var Y = 4;
// Function Call
getMinDifference(arr, N, Y);
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA