Dada una array arr[] de enteros. La tarea es encontrar los índices de todos los mínimos y máximos locales en la array dada.
Ejemplos:
Entrada: arr = [100, 180, 260, 310, 40, 535, 695]
Salida:
Puntos de mínimos locales: 0 4 Puntos de máximos locales: 3 6 Explicación: La array dada puede dividirse como se muestra a continuación en las sub-arrays: 1. primer subconjunto [100, 180, 260, 310] índice de mínimos locales = 0 índice de máximos locales = 3 2. segundo subconjunto [40, 535, 695] índice de mínimos locales = 4 índice de máximos locales = 6
Entrada: arr = [23, 13, 25, 29, 33, 19, 34, 45, 65, 67]
Salida:
Puntos de mínimos locales: 1 5
Puntos de máximos locales: 0 4 9
Enfoque: la idea es iterar sobre la array dada arr[] y verificar si cada elemento de la array es el más pequeño o el más grande entre sus elementos adyacentes. Si es el más pequeño, entonces es un mínimo local y si es el más grande, entonces es un máximo local. A continuación se muestran los pasos:
- Cree dos arrays max[] y min[] para almacenar todos los máximos y mínimos locales.
- Recorra la array dada y agregue el índice de la array en la array max[] y min[] de acuerdo con las siguientes condiciones:
- Si arr[i – 1] > arr[i] < arr[i + 1], agregue ese índice a min[] .
- Si arr[i – 1] < arr[i] > arr[i + 1], agregue ese índice a max[] .
- Compruebe las condiciones máximas y mínimas locales para el primer y el último elemento por separado.
- Imprime los índices almacenados en min[] y max[] .
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 all the local maxima
// and minima in the given array arr[]
void findLocalMaximaMinima(int n, int arr[])
{
// Empty vector to store points of
// local maxima and minima
vector<int> mx, mn;
// Checking whether the first point is
// local maxima or minima or none
if (arr[0] > arr[1])
mx.push_back(0);
else if (arr[0] < arr[1])
mn.push_back(0);
// Iterating over all points to check
// local maxima and local minima
for(int i = 1; i < n - 1; i++)
{
// Condition for local minima
if ((arr[i - 1] > arr[i]) and
(arr[i] < arr[i + 1]))
mn.push_back(i);
// Condition for local maxima
else if ((arr[i - 1] < arr[i]) and
(arr[i] > arr[i + 1]))
mx.push_back(i);
}
// Checking whether the last point is
// local maxima or minima or none
if (arr[n - 1] > arr[n - 2])
mx.push_back(n - 1);
else if (arr[n - 1] < arr[n - 2])
mn.push_back(n - 1);
// Print all the local maxima and
// local minima indexes stored
if (mx.size() > 0)
{
cout << "Points of Local maxima are : ";
for(int a : mx)
cout << a << " ";
cout << endl;
}
else
cout << "There are no points of "
<< "Local Maxima \n";
if (mn.size() > 0)
{
cout << "Points of Local minima are : ";
for(int a : mn)
cout << a << " ";
cout << endl;
}
else
cout << "There are no points of "
<< "Local Minima \n";
}
// Driver Code
int main()
{
int N = 9;
// Given array arr[]
int arr[] = { 10, 20, 15, 14, 13,
25, 5, 4, 3 };
// Function call
findLocalMaximaMinima(N, arr);
return 0;
}
// This code is contributed by himanshu77
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find all the local maxima
// and minima in the given array arr[]
public static void findLocalMaximaMinima(int n,
int[] arr)
{
// Empty vector to store points of
// local maxima and minima
Vector<Integer> mx = new Vector<Integer>();
Vector<Integer> mn = new Vector<Integer>();
// Checking whether the first point is
// local maxima or minima or none
if (arr[0] > arr[1])
mx.add(0);
else if (arr[0] < arr[1])
mn.add(0);
// Iterating over all points to check
// local maxima and local minima
for(int i = 1; i < n - 1; i++)
{
// Condition for local minima
if ((arr[i - 1] > arr[i]) &&
(arr[i] < arr[i + 1]))
mn.add(i);
// Condition for local maxima
else if ((arr[i - 1] < arr[i]) &&
(arr[i] > arr[i + 1]))
mx.add(i);
}
// Checking whether the last point is
// local maxima or minima or none
if (arr[n - 1] > arr[n - 2])
mx.add(n - 1);
else if (arr[n - 1] < arr[n - 2])
mn.add(n - 1);
// Print all the local maxima and
// local minima indexes stored
if (mx.size() > 0)
{
System.out.print("Points of Local " +
"maxima are : ");
for(Integer a : mx)
System.out.print(a + " ");
System.out.println();
}
else
System.out.println("There are no points " +
"of Local Maxima ");
if (mn.size() > 0)
{
System.out.print("Points of Local " +
"minima are : ");
for(Integer a : mn)
System.out.print(a + " ");
System.out.println();
}
else
System.out.println("There are no points of " +
"Local Maxima ");
}
// Driver code
public static void main(String[] args)
{
int N = 9;
// Given array arr[]
int arr[] = { 10, 20, 15, 14, 13,
25, 5, 4, 3 };
// Function call
findLocalMaximaMinima(N, arr);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach
# Function to find all the local maxima
# and minima in the given array arr[]
def findLocalMaximaMinima(n, arr):
# Empty lists to store points of
# local maxima and minima
mx = []
mn = []
# Checking whether the first point is
# local maxima or minima or neither
if(arr[0] > arr[1]):
mx.append(0)
elif(arr[0] < arr[1]):
mn.append(0)
# Iterating over all points to check
# local maxima and local minima
for i in range(1, n-1):
# Condition for local minima
if(arr[i-1] > arr[i] < arr[i + 1]):
mn.append(i)
# Condition for local maxima
elif(arr[i-1] < arr[i] > arr[i + 1]):
mx.append(i)
# Checking whether the last point is
# local maxima or minima or neither
if(arr[-1] > arr[-2]):
mx.append(n-1)
elif(arr[-1] < arr[-2]):
mn.append(n-1)
# Print all the local maxima and
# local minima indexes stored
if(len(mx) > 0):
print("Points of Local maxima"\
" are : ", end ='')
print(*mx)
else:
print("There are no points of"\
" Local maxima.")
if(len(mn) > 0):
print("Points of Local minima"\
" are : ", end ='')
print(*mn)
else:
print("There are no points"\
" of Local minima.")
# Driver Code
if __name__ == '__main__':
N = 9
# Given array arr[]
arr = [10, 20, 15, 14, 13, 25, 5, 4, 3]
# Function Call
findLocalMaximaMinima(N, arr)
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to find all the local maxima
// and minima in the given array arr[]
public static void findLocalMaximaMinima(int n,
int[] arr)
{
// Empty vector to store points of
// local maxima and minima
ArrayList mx = new ArrayList();
ArrayList mn = new ArrayList();
// Checking whether the first point is
// local maxima or minima or none
if (arr[0] > arr[1])
mx.Add(0);
else if (arr[0] < arr[1])
mn.Add(0);
// Iterating over all points to check
// local maxima and local minima
for(int i = 1; i < n - 1; i++)
{
// Condition for local minima
if ((arr[i - 1] > arr[i]) &&
(arr[i] < arr[i + 1]))
mn.Add(i);
// Condition for local maxima
else if ((arr[i - 1] < arr[i]) &&
(arr[i] > arr[i + 1]))
mx.Add(i);
}
// Checking whether the last point is
// local maxima or minima or none
if (arr[n - 1] > arr[n - 2])
mx.Add(n - 1);
else if (arr[n - 1] < arr[n - 2])
mn.Add(n - 1);
// Print all the local maxima and
// local minima indexes stored
if (mx.Count > 0)
{
Console.Write("Points of Local " +
"maxima are : ");
foreach(int a in mx)
Console.Write(a + " ");
Console.Write("\n");
}
else
Console.Write("There are no points " +
"of Local Maxima ");
if (mn.Count > 0)
{
Console.Write("Points of Local " +
"minima are : ");
foreach(int a in mn)
Console.Write(a + " ");
Console.Write("\n");
}
else
Console.Write("There are no points of " +
"Local Maxima ");
}
// Driver code
public static void Main(string[] args)
{
int N = 9;
// Given array arr[]
int []arr = { 10, 20, 15, 14, 13,
25, 5, 4, 3 };
// Function call
findLocalMaximaMinima(N, arr);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program for the above approach
// Function to find all the local maxima
// and minima in the given array arr[]
function findLocalMaximaMinima(n, arr)
{
// Empty vector to store points of
// local maxima and minima
let mx = [], mn = [];
// Checking whether the first point is
// local maxima or minima or none
if (arr[0] > arr[1])
mx.push(0);
else if (arr[0] < arr[1])
mn.push(0);
// Iterating over all points to check
// local maxima and local minima
for(let i = 1; i < n - 1; i++)
{
// Condition for local minima
if ((arr[i - 1] > arr[i]) &&
(arr[i] < arr[i + 1]))
mn.push(i);
// Condition for local maxima
else if ((arr[i - 1] < arr[i]) &&
(arr[i] > arr[i + 1]))
mx.push(i);
}
// Checking whether the last point is
// local maxima or minima or none
if (arr[n - 1] > arr[n - 2])
mx.push(n - 1);
else if (arr[n - 1] < arr[n - 2])
mn.push(n - 1);
// Print all the local maxima and
// local minima indexes stored
if (mx.length > 0)
{
document.write("Points of Local maxima are : ");
for(let a of mx){
document.write(a," ");
}
document.write("</br>");
}
else
document.write("There are no points of Local Maxima ","</br>");
if (mn.length > 0)
{
document.write("Points of Local minima are : ");
for(let a of mn){
document.write(a," ");
}
document.write("</br>");
}
else
document.write("There are no points of Local Minima","</br>");
}
// Driver Code
let N = 9;
// Given array arr[]
let arr = [ 10, 20, 15, 14, 13, 25, 5, 4, 3 ];
// Function call
findLocalMaximaMinima(N, arr);
// This code is contributed by shinjanpatra
</script>
Producción:
Points of Local maxima are : 1 5 Points of Local minima are : 0 4 8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por arjunsaini9081 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA