Dada una array arr[] de longitud N , la tarea es encontrar el número de elementos en la array arr[] que contiene al menos un elemento más pequeño a su izquierda y derecha .
Ejemplos:
Entrada: arr[] = {3, 9, 4, 6, 7, 5}
Salida: 3
Explicación: Los siguientes 3 elementos de la array satisfacen las condiciones necesarias:
- arr[1] (= 9) tiene un elemento más pequeño a la izquierda como 3 y a la derecha como 4
- arr[3] (= 6) tiene un elemento más pequeño a la izquierda como 4 y a la derecha como 5.
- arr[4] (= 7) tiene un elemento más pequeño a la izquierda como 6 y a la derecha como 5.
Entrada: arr[] = {3, 9, 14, 61, 17, 5, 12, 9, 15}
Salida: 5
Enfoque ingenuo: el enfoque más simple es recorrer la array dada y, para cada elemento, contar la cantidad de elementos más pequeños tanto a la izquierda como a la derecha. Si se encuentra que ambos conteos son al menos 1 , aumente la respuesta en 1 . Finalmente, imprime la respuesta obtenida.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar un Stack . Mantenga una pila creciente de elementos para contar el elemento más pequeño en tiempo constante. Siga los pasos a continuación para resolver el problema:
- Inicialice una pila y un conteo variable como 0 como un conteo de números que satisfacen la condición dada.
- Recorra la array dada usando la variable i y realice los siguientes pasos:
- Iterar hasta que la pila no esté vacía y el elemento actual sea menor que el elemento superior de la pila , entonces:
- El elemento en la parte superior de la pila tiene un elemento más pequeño a la derecha, es decir, arr[i] .
- Si el tamaño de la pila es mayor que 1 , también hay un elemento más pequeño a la izquierda, ya que la pila se ha mantenido como una pila creciente.
- Si las condiciones anteriores son verdaderas , incremente el conteo en 1 .
- Extraiga el elemento superior de la pila .
- Empuje el elemento actual en la pila.
- Iterar hasta que la pila no esté vacía y el elemento actual sea menor que el elemento superior de la pila , entonces:
- Después de los pasos anteriores, el valor de cuenta da la cuenta resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to count the number of
// elements that have smaller on
// left and right side
void findElements(int* arr, int N)
{
// Initialize stack
stack<int> stack;
// Stores the required count
// of array elements
int count = 0;
// Traverse the array A{]
for (int i = 0; i < N; i++) {
// If stack is not empty
// and stack top > arr[i]
while (!stack.empty()
&& arr[i] < stack.top()) {
// If stack size > 1
if (stack.size() > 1)
// Increment count
count++;
// Pop the top element
stack.pop();
}
// Push the element arr[i]
stack.push(arr[i]);
}
// Print the final count
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 3, 9, 4, 6, 7, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
findElements(arr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to count the number of
// elements that have smaller on
// left and right side
static void findElements(int[] arr,
int N)
{
// Initialize stack
Stack<Integer> stack = new Stack<>();
// Stores the required count
// of array elements
int count = 0;
// Traverse the array A[]
for (int i = 0; i < N; i++)
{
// If stack is not empty
// and stack top > arr[i]
while (!stack.isEmpty() &&
arr[i] < stack.peek())
{
// If stack size > 1
if (stack.size() > 1)
// Increment count
count++;
// Pop the top element
stack.pop();
}
// Push the element arr[i]
stack.add(arr[i]);
}
// Print the final count
System.out.print(count);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {3, 9, 4, 6, 7, 5};
int N = arr.length;
// Function Call
findElements(arr, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
# Function to count the number of
# elements that have smaller on
# left and right side
def findElements(arr, N):
# Initialize stack
stack = []
# Stores the required count
# of array elements
count = 0
# Traverse the array A{]
for i in range(N):
# If stack is not empty
# and stack top > arr[i]
while (len(stack) > 0 and
arr[i] < stack[-1]):
# If stack size > 1
if (len(stack) > 1):
# Increment count
count += 1
# Pop the top element
del stack[-1]
# Push the element arr[i]
stack.append(arr[i])
# Print the final count
print(count)
# Driver Code
if __name__ == '__main__':
arr = [ 3, 9, 4, 6, 7, 5 ]
N = len(arr)
# Function Call
findElements(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the number of
// elements that have smaller on
// left and right side
static void findElements(int[] arr, int N)
{
// Initialize stack
Stack<int> stack = new Stack<int>();
// Stores the required count
// of array elements
int count = 0;
// Traverse the array A{]
for(int i = 0; i < N; i++)
{
// If stack is not empty
// and stack top > arr[i]
while (stack.Count != 0 &&
arr[i] < stack.Peek())
{
// If stack size > 1
if (stack.Count > 1)
// Increment count
count++;
// Pop the top element
stack.Pop();
}
// Push the element arr[i]
stack.Push(arr[i]);
}
// Print the readonly count
Console.Write(count);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 9, 4, 6, 7, 5 };
int N = arr.Length;
// Function Call
findElements(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to count the number of
// elements that have smaller on
// left and right side
function findElements(arr, N)
{
// Initialize stack
var stack = [];
// Stores the required count
// of array elements
var count = 0;
// Traverse the array A{]
for (var i = 0; i < N; i++) {
// If stack is not empty
// and stack top > arr[i]
while (stack.length!=0
&& arr[i] < stack[stack.length-1]) {
// If stack size > 1
if (stack.length > 1)
// Increment count
count++;
// Pop the top element
stack.pop();
}
// Push the element arr[i]
stack.push(arr[i]);
}
// Print the final count
document.write( count);
}
// Driver Code
var arr = [3, 9, 4, 6, 7, 5];
var N = arr.length;
// Function Call
findElements(arr, N);
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA