Dada una array arr[] que consta de N enteros y una array Q[][] que consta de consultas de la forma [L, R]. , la tarea de cada consulta es encontrar los elementos de array máximos y mínimos en la array, excluyendo los elementos del rango dado.
Ejemplos:
Entrada: arr[] = {2, 3, 1, 8, 3, 5, 7, 4}, Q[][] = {{4, 6}, {0, 4}, {3, 7}, { 2, 5}}
Salida:
8 1
7 4
3 1
7 2
Explicación:
Consulta 1: max(arr[0, 1, …, 3], arr[7]) = 8 and min(arr[0, 1, … , 3], arr[7]) = 1
Consulta 2: max(arr[5, 6, …, 7]) = 7 y min(arr[5, 6, …, 7]) = 4
Consulta 3: max( arr[0, 1, …, 2]) =3 y min(arr[0, 1, …, 2]) = 1
Consulta 4: max(arr[0, 1], arr[6, …, 7]) =7 y min(arr[0, 1], arr[6, …, 7]) = 2Entrada: arr[] = {3, 2, 1, 4, 5}, Q[][] = {{1, 2}, {2, 4}}
Salida:
5 3
3 2
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array para cada consulta y encontrar los elementos máximo y mínimo presentes fuera del rango de índices [L, R] .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: divida el problema en subtareas dividiendo la array en subrangos y encuentre el valor máximo y mínimo de arr[0] a arr[L – 1] y de arr[r + 1] a arr[N – 1] y almacenarlos en una array de prefijos y sufijos respectivamente. Ahora encuentre los valores máximo y mínimo para los rangos dados comparando el prefijo y la array de sufijos.
Siga los pasos a continuación:
- Recorra la array y mantenga los elementos máximos y mínimos encontrados para cada índice en una array de prefijos 2D comparando el valor en el índice actual con los valores máximo y mínimo del índice anterior.
- Ahora, itere sobre la array a la inversa y mantenga los valores máximo y mínimo para los índices en la array de sufijos 2D comparando el valor en el índice actual con los valores máximo y mínimo del siguiente índice.
- Ahora, para cada consulta, realice los siguientes pasos:
- Si L = 0 y R = N – 1 , no queda ningún elemento después de excluir el rango.
- De lo contrario, si L = 0 , el valor máximo y mínimo estará presente entre arr[R + 1] a arr[N – 1] .
- De lo contrario, si R = N – 1 , el valor máximo y mínimo estará presente entre arr[0] y arr[L – 1] .
- De lo contrario, encuentre los valores máximo y mínimo en el rango arr[0] a arr[L – 1] y arr[R + 1] a arr[N – 1] .
- Imprime los valores máximo y mínimo para esta consulta.
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 find the maximum and
// minimum array elements up to the i-th index
void prefixArr(int arr[], int prefix[][2], int N)
{
// Traverse the array
for (int i = 0; i < N; i++) {
if (i == 0) {
prefix[i][0] = arr[i];
prefix[i][1] = arr[i];
}
else {
// Compare current value with maximum
// and minimum values up to previous index
prefix[i][0] = max(prefix[i - 1][0], arr[i]);
prefix[i][1] = min(prefix[i - 1][1], arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements from i-th index
void suffixArr(int arr[], int suffix[][2], int N)
{
// Traverse the array in reverse
for (int i = N - 1; i >= 0; i--) {
if (i == N - 1) {
suffix[i][0] = arr[i];
suffix[i][1] = arr[i];
}
else {
// Compare current value with maximum
// and minimum values in the next index
suffix[i][0] = max(suffix[i + 1][0], arr[i]);
suffix[i][1] = min(suffix[i + 1][1], arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements for each query
void maxAndmin(int prefix[][2],
int suffix[][2],
int N, int L, int R)
{
int maximum, minimum;
// If no index remains after
// excluding the elements
// in a given range
if (L == 0 && R == N - 1) {
cout << "No maximum and minimum value" << endl;
return;
}
// Find maximum and minimum from
// from the range [R + 1, N - 1]
else if (L == 0) {
maximum = suffix[R + 1][0];
minimum = suffix[R + 1][1];
}
// Find maximum and minimum from
// from the range [0, N - 1]
else if (R == N - 1) {
maximum = prefix[L - 1][0];
minimum = prefix[R - 1][1];
}
// Find maximum and minimum values from the
// ranges [0, L - 1] and [R + 1, N - 1]
else {
maximum = max(prefix[L - 1][0],
suffix[R + 1][0]);
minimum = min(prefix[L - 1][1],
suffix[R + 1][1]);
}
// Print the maximum and minimum value
cout << maximum << " " << minimum << endl;
}
// Function to perform queries to find the
// minimum and maximum array elements excluding
// elements from a given range
void MinMaxQueries(int a[], int Q[][])
{
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Size of query array
int q = sizeof(queries) / sizeof(queries[0]);
// prefix[i][0]: Stores the maximum
// prefix[i][1]: Stores the minimum value
int prefix[N][2];
// suffix[i][0]: Stores the maximum
// suffix[i][1]: Stores the minimum value
int suffix[N][2];
// Function calls to store
// maximum and minimum values
// for respective ranges
prefixArr(arr, prefix, N);
suffixArr(arr, suffix, N);
for (int i = 0; i < q; i++) {
int L = queries[i][0];
int R = queries[i][1];
maxAndmin(prefix, suffix, N, L, R);
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 3, 1, 8, 3, 5, 7, 4 };
int queries[][2]
= { { 4, 6 }, { 0, 4 }, { 3, 7 }, { 2, 5 } };
MinMaxQueries(arr, Q);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to find the maximum and
// minimum array elements up to the i-th index
static void prefixArr(int arr[], int prefix[][], int N)
{
// Traverse the array
for (int i = 0; i < N; i++)
{
if (i == 0)
{
prefix[i][0] = arr[i];
prefix[i][1] = arr[i];
}
else
{
// Compare current value with maximum
// and minimum values up to previous index
prefix[i][0] = Math.max(prefix[i - 1][0], arr[i]);
prefix[i][1] = Math.min(prefix[i - 1][1], arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements from i-th index
static void suffixArr(int arr[], int suffix[][], int N)
{
// Traverse the array in reverse
for (int i = N - 1; i >= 0; i--)
{
if (i == N - 1)
{
suffix[i][0] = arr[i];
suffix[i][1] = arr[i];
}
else
{
// Compare current value with maximum
// and minimum values in the next index
suffix[i][0] = Math.max(suffix[i + 1][0], arr[i]);
suffix[i][1] = Math.min(suffix[i + 1][1], arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements for each query
static void maxAndmin(int prefix[][],
int suffix[][],
int N, int L, int R)
{
int maximum, minimum;
// If no index remains after
// excluding the elements
// in a given range
if (L == 0 && R == N - 1)
{
System.out.println("No maximum and minimum value");
return;
}
// Find maximum and minimum from
// from the range [R + 1, N - 1]
else if (L == 0)
{
maximum = suffix[R + 1][0];
minimum = suffix[R + 1][1];
}
// Find maximum and minimum from
// from the range [0, N - 1]
else if (R == N - 1)
{
maximum = prefix[L - 1][0];
minimum = prefix[R - 1][1];
}
// Find maximum and minimum values from the
// ranges [0, L - 1] and [R + 1, N - 1]
else
{
maximum = Math.max(prefix[L - 1][0],
suffix[R + 1][0]);
minimum = Math.min(prefix[L - 1][1],
suffix[R + 1][1]);
}
// Print the maximum and minimum value
System.out.println(maximum + " " + minimum);
}
// Function to perform queries to find the
// minimum and maximum array elements excluding
// elements from a given range
static void MinMaxQueries(int a[], int Q[][])
{
// Size of the array
int N = a.length;
// Size of query array
int q = Q.length;
// prefix[i][0]: Stores the maximum
// prefix[i][1]: Stores the minimum value
int prefix[][] = new int[N][2];
// suffix[i][0]: Stores the maximum
// suffix[i][1]: Stores the minimum value
int suffix[][] = new int[N][2];
// Function calls to store
// maximum and minimum values
// for respective ranges
prefixArr(a, prefix, N);
suffixArr(a, suffix, N);
for (int i = 0; i < q; i++)
{
int L = Q[i][0];
int R = Q[i][1];
maxAndmin(prefix, suffix, N, L, R);
}
}
// Driver Code
public static void main (String[] args)
{
// Given array
int arr[] = { 2, 3, 1, 8, 3, 5, 7, 4 };
int queries[][]
= { { 4, 6 }, { 0, 4 }, { 3, 7 }, { 2, 5 } };
MinMaxQueries(arr, queries);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach
# Function to find the maximum and
# minimum array elements up to the i-th index
def prefixArr(arr, prefix, N):
# Traverse the array
for i in range(N):
if (i == 0):
prefix[i][0] = arr[i]
prefix[i][1] = arr[i]
else:
# Compare current value with maximum
# and minimum values up to previous index
prefix[i][0] = max(prefix[i - 1][0], arr[i])
prefix[i][1] = min(prefix[i - 1][1], arr[i])
return prefix
# Function to find the maximum and
# minimum array elements from i-th index
def suffixArr(arr, suffix, N):
# Traverse the array in reverse
for i in range(N - 1, -1, -1):
if (i == N - 1):
suffix[i][0] = arr[i]
suffix[i][1] = arr[i]
else:
# Compare current value with maximum
# and minimum values in the next index
suffix[i][0] = max(suffix[i + 1][0], arr[i])
suffix[i][1] = min(suffix[i + 1][1], arr[i])
return suffix
# Function to find the maximum and
# minimum array elements for each query
def maxAndmin(prefix, suffix, N, L, R):
maximum, minimum = 0, 0
# If no index remains after
# excluding the elements
# in a given range
if (L == 0 and R == N - 1):
print("No maximum and minimum value")
return
# Find maximum and minimum from
# from the range [R + 1, N - 1]
elif (L == 0):
maximum = suffix[R + 1][0]
minimum = suffix[R + 1][1]
# Find maximum and minimum from
# from the range [0, N - 1]
elif (R == N - 1):
maximum = prefix[L - 1][0]
minimum = prefix[R - 1][1]
# Find maximum and minimum values from the
# ranges [0, L - 1] and [R + 1, N - 1]
else:
maximum = max(prefix[L - 1][0], suffix[R + 1][0])
minimum = min(prefix[L - 1][1], suffix[R + 1][1])
# Print maximum and minimum value
print(maximum, minimum)
# Function to perform queries to find the
# minimum and maximum array elements excluding
# elements from a given range
def MinMaxQueries(a, queries):
# Size of the array
N = len(arr)
# Size of query array
q = len(queries)
# prefix[i][0]: Stores the maximum
# prefix[i][1]: Stores the minimum value
prefix = [ [ 0 for i in range(2)] for i in range(N)]
# suffix[i][0]: Stores the maximum
# suffix[i][1]: Stores the minimum value
suffix = [ [ 0 for i in range(2)] for i in range(N)]
# Function calls to store
# maximum and minimum values
# for respective ranges
prefix = prefixArr(arr, prefix, N)
suffix = suffixArr(arr, suffix, N)
for i in range(q):
L = queries[i][0]
R = queries[i][1]
maxAndmin(prefix, suffix, N, L, R)
# Driver Code
if __name__ == '__main__':
# Given array
arr = [ 2, 3, 1, 8, 3, 5, 7, 4 ]
queries = [ [ 4, 6 ], [ 0, 4 ], [ 3, 7 ], [ 2, 5 ] ]
MinMaxQueries(arr, queries)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the maximum and
// minimum array elements up to the i-th index
static void prefixArr(int[] arr, int[,] prefix, int N)
{
// Traverse the array
for (int i = 0; i < N; i++)
{
if (i == 0)
{
prefix[i, 0] = arr[i];
prefix[i, 1] = arr[i];
}
else
{
// Compare current value with maximum
// and minimum values up to previous index
prefix[i, 0] = Math.Max(prefix[i - 1, 0], arr[i]);
prefix[i, 1] = Math.Min(prefix[i - 1, 1], arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements from i-th index
static void suffixArr(int[] arr, int[,] suffix, int N)
{
// Traverse the array in reverse
for (int i = N - 1; i >= 0; i--)
{
if (i == N - 1)
{
suffix[i, 0] = arr[i];
suffix[i, 1] = arr[i];
}
else
{
// Compare current value with maximum
// and minimum values in the next index
suffix[i, 0] = Math.Max(suffix[i + 1, 0], arr[i]);
suffix[i, 1] = Math.Min(suffix[i + 1, 1], arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements for each query
static void maxAndmin(int[,] prefix,
int[,] suffix,
int N, int L, int R)
{
int maximum, minimum;
// If no index remains after
// excluding the elements
// in a given range
if (L == 0 && R == N - 1)
{
Console.WriteLine("No maximum and minimum value");
return;
}
// Find maximum and minimum from
// from the range [R + 1, N - 1]
else if (L == 0)
{
maximum = suffix[R + 1, 0];
minimum = suffix[R + 1, 1];
}
// Find maximum and minimum from
// from the range [0, N - 1]
else if (R == N - 1)
{
maximum = prefix[L - 1, 0];
minimum = prefix[R - 1, 1];
}
// Find maximum and minimum values from the
// ranges [0, L - 1] and [R + 1, N - 1]
else
{
maximum = Math.Max(prefix[L - 1, 0],
suffix[R + 1, 0]);
minimum = Math.Min(prefix[L - 1, 1],
suffix[R + 1, 1]);
}
// Print the maximum and minimum value
Console.WriteLine(maximum + " " + minimum);
}
// Function to perform queries to find the
// minimum and maximum array elements excluding
// elements from a given range
static void MinMaxQueries(int[] a, int[,] Q)
{
// Size of the array
int N = a.GetLength(0);
// Size of query array
int q = Q.GetLength(0);
// prefix[i][0]: Stores the maximum
// prefix[i][1]: Stores the minimum value
int[,] prefix = new int[N, 2];
// suffix[i][0]: Stores the maximum
// suffix[i][1]: Stores the minimum value
int[,] suffix = new int[N, 2];
// Function calls to store
// maximum and minimum values
// for respective ranges
prefixArr(a, prefix, N);
suffixArr(a, suffix, N);
for (int i = 0; i < q; i++)
{
int L = Q[i, 0];
int R = Q[i, 1];
maxAndmin(prefix, suffix, N, L, R);
}
}
// Driver Code
static public void Main ()
{
// Given array
int[] arr = { 2, 3, 1, 8, 3, 5, 7, 4 };
int[,] queries = { { 4, 6 }, { 0, 4 },
{ 3, 7 }, { 2, 5 } };
MinMaxQueries(arr, queries);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum and
// minimum array elements up to the i-th index
function prefixArr(arr, prefix, N)
{
// Traverse the array
for (var i = 0; i < N; i++) {
if (i == 0) {
prefix[i][0] = arr[i];
prefix[i][1] = arr[i];
}
else {
// Compare current value with maximum
// and minimum values up to previous index
prefix[i][0] = Math.max(prefix[i - 1][0],
arr[i]);
prefix[i][1] = Math.min(prefix[i - 1][1],
arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements from i-th index
function suffixArr(arr, suffix, N)
{
// Traverse the array in reverse
for (var i = N - 1; i >= 0; i--) {
if (i == N - 1) {
suffix[i][0] = arr[i];
suffix[i][1] = arr[i];
}
else {
// Compare current value with maximum
// and minimum values in the next index
suffix[i][0] = Math.max(suffix[i + 1][0],
arr[i]);
suffix[i][1] = Math.min(suffix[i + 1][1],
arr[i]);
}
}
}
// Function to find the maximum and
// minimum array elements for each query
function maxAndmin(prefix, suffix, N, L, R)
{
var maximum, minimum;
// If no index remains after
// excluding the elements
// in a given range
if (L == 0 && R == N - 1) {
document.write( "No maximum and minimum value" +
"<br>");
return;
}
// Find maximum and minimum from
// from the range [R + 1, N - 1]
else if (L == 0) {
maximum = suffix[R + 1][0];
minimum = suffix[R + 1][1];
}
// Find maximum and minimum from
// from the range [0, N - 1]
else if (R == N - 1) {
maximum = prefix[L - 1][0];
minimum = prefix[R - 1][1];
}
// Find maximum and minimum values from the
// ranges [0, L - 1] and [R + 1, N - 1]
else {
maximum = Math.max(prefix[L - 1][0],
suffix[R + 1][0]);
minimum = Math.min(prefix[L - 1][1],
suffix[R + 1][1]);
}
// Print the maximum and minimum value
document.write( maximum + " " + minimum + "<br>");
}
// Function to perform queries to find the
// minimum and maximum array elements excluding
// elements from a given range
function MinMaxQueries(a, Q)
{
// Size of the array
var N = arr.length;
// Size of query array
var q = queries.length;
// prefix[i][0]: Stores the maximum
// prefix[i][1]: Stores the minimum value
var prefix = Array.from(Array(N), ()=> Array(2));
// suffix[i][0]: Stores the maximum
// suffix[i][1]: Stores the minimum value
var suffix = Array.from(Array(N), ()=> Array(2));
// Function calls to store
// maximum and minimum values
// for respective ranges
prefixArr(arr, prefix, N);
suffixArr(arr, suffix, N);
for (var i = 0; i < q; i++) {
var L = queries[i][0];
var R = queries[i][1];
maxAndmin(prefix, suffix, N, L, R);
}
}
// Driver Code
// Given array
var arr = [2, 3, 1, 8, 3, 5, 7, 4 ];
var queries
= [ [ 4, 6 ], [ 0, 4 ], [ 3, 7 ], [ 2, 5 ] ];
MinMaxQueries(arr, queries);
</script>
Producción:
8 1 7 4 3 1 7 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por adarsh_sinhg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA