Recuento de elementos de Array mayor que todos los elementos a su izquierda y los siguientes K elementos a su derecha

Dada una array arr[] , la tarea es imprimir el número de elementos que son mayores que todos los elementos a su izquierda, así como mayores que los siguientes K elementos a su derecha.

Ejemplos: 
 

Entrada: arr[] = { 4, 2, 3, 6, 4, 3, 2}, K = 2 
Salida: 2 
Explicación: 
arr[0](= 4): arr[0] es el primer elemento de la array y mayor que sus siguientes K(= 2) elementos {2, 3}. 
arr[2](= 6): arr[2] es mayor que todos los elementos a su izquierda {4, 2, 3} y mayor que sus siguientes K(= 2) elementos {4, 3}. 
Por lo tanto, solo dos elementos satisfacen la condición dada.
Entrada: arr[] = { 3, 1, 2, 7, 5, 1, 2, 6}, K = 2 
Salida: 2 
 

Enfoque ingenuo: 
recorra la array y, para cada elemento, verifique si todos los elementos a su izquierda son más pequeños que él, así como los siguientes elementos K a su derecha son más pequeños que él. Para cada uno de esos elementos, aumente el conteo . Finalmente, imprima el conteo . 
Complejidad de tiempo: O(N ² ) 
Espacio auxiliar: O(1)
Enfoque eficiente: 
El enfoque anterior se puede optimizar mediante el uso de la estructura de datos de pila . Siga los pasos a continuación para resolver el problema: 
 

1. Inicialice una nueva array y almacene el índice del siguiente elemento mayor para cada elemento de la array mediante Stack .
2. Recorra la array dada y para cada elemento, verifique si es el máximo obtenido hasta el momento y si su siguiente elemento mayor tiene al menos K índices después del índice actual. Si se determina que es cierto, aumente la cuenta .
3. Finalmente, imprima el conteo . 
    

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the count of
// Array elements greater than all
// elements on its left and next K
// elements on its right
int countElements(int arr[], int n,
                  int k)
{
 
    stack<int> s;
 
    vector<int> next_greater(n, n + 1);
 
    // Iterate over the array
    for (int i = 0; i < n; i++) {
 
        if (s.empty()) {
            s.push(i);
            continue;
        }
 
        // If the stack is not empty and
        // the element at the top of the
        // stack is smaller than arr[i]
        while (!s.empty()
               && arr[s.top()] < arr[i]) {
            // Store the index of next
            // greater element
            next_greater[s.top()] = i;
 
            // Pop the top element
            s.pop();
        }
 
        // Insert the current index
        s.push(i);
    }
 
    // Stores the count
    int count = 0;
    int maxi = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (next_greater[i] - i > k
            && maxi < arr[i]) {
            maxi = max(maxi, arr[i]);
            count++;
        }
    }
 
    return count;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 4, 2, 3, 6, 4, 3, 2 };
    int K = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countElements(arr, n, K);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to print the count of
// Array elements greater than all
// elements on its left and next K
// elements on its right
static int countElements(int arr[], int n,
                                    int k)
{
    Stack<Integer> s = new Stack<Integer>();
 
    int []next_greater = new int[n + 1];
    Arrays.fill(next_greater, n);
 
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        if (s.isEmpty())
        {
            s.add(i);
            continue;
        }
 
        // If the stack is not empty and
        // the element at the top of the
        // stack is smaller than arr[i]
        while (!s.isEmpty() &&
               arr[s.peek()] < arr[i])
        {
             
            // Store the index of next
            // greater element
            next_greater[s.peek()] = i;
 
            // Pop the top element
            s.pop();
        }
 
        // Insert the current index
        s.add(i);
    }
 
    // Stores the count
    int count = 0;
    int maxi = Integer.MIN_VALUE;
     
    for(int i = 0; i < n; i++)
    {
        if (next_greater[i] - i > k &&
              maxi < arr[i])
        {
            maxi = Math.max(maxi, arr[i]);
            count++;
        }
    }
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 4, 2, 3, 6, 4, 3, 2 };
    int K = 2;
    int n = arr.length;
     
    System.out.print(countElements(arr, n, K));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to implement
# the above approach
import sys
 
# Function to print the count of
# Array elements greater than all
# elements on its left and next K
# elements on its right
def countElements(arr, n, k):
 
    s = []
 
    next_greater = [n] * (n + 1)
 
    # Iterate over the array
    for i in range(n):
        if(len(s) == 0):
            s.append(i)
            continue
 
        # If the stack is not empty and
        # the element at the top of the
        # stack is smaller than arr[i]
        while(len(s) != 0 and
              arr[s[-1]] < arr[i]):
                   
            # Store the index of next
            # greater element
            next_greater[s[-1]] = i
 
            # Pop the top element
            s.pop(-1)
 
        # Insert the current index
        s.append(i)
 
    # Stores the count
    count = 0
    maxi = -sys.maxsize - 1
     
    for i in range(n):
        if(next_greater[i] - i > k and
             maxi < arr[i]):
            maxi = max(maxi, arr[i])
            count += 1
 
    return count
 
# Driver Code
if __name__ == '__main__':
 
    arr = [ 4, 2, 3, 6, 4, 3, 2 ]
    K = 2
    n = len(arr)
 
    # Function call
    print(countElements(arr, n, K))
 
# This code is contributed by Shivam Singh

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to print the count of
// Array elements greater than all
// elements on its left and next K
// elements on its right
static int countElements(int[] arr, int n,
                         int k)
{
    Stack<int> s = new Stack<int>();
 
    int[] next_greater = new int[n + 1];
    Array.Fill(next_greater, n);
 
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        if (s.Count == 0)
        {
            s.Push(i);
            continue;
        }
 
        // If the stack is not empty and
        // the element at the top of the
        // stack is smaller than arr[i]
        while (s.Count != 0 &&
               arr[s.Peek()] < arr[i])
        {
             
            // Store the index of next
            // greater element
            next_greater[s.Peek()] = i;
 
            // Pop the top element
            s.Pop();
        }
 
        // Insert the current index
        s.Push(i);
    }
 
    // Stores the count
    int count = 0;
    int maxi = Int32.MinValue;
     
    for(int i = 0; i < n; i++)
    {
        if (next_greater[i] - i > k &&
                       maxi < arr[i])
        {
            maxi = Math.Max(maxi, arr[i]);
            count++;
        }
    }
    return count;
}
 
// Driver Code
static void Main()
{
    int[] arr = { 4, 2, 3, 6, 4, 3, 2 };
    int K = 2;
    int n = arr.Length;
 
    Console.Write(countElements(arr, n, K));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
      // JavaScript program to implement
      // the above approach
       
      // Function to print the count of
      // Array elements greater than all
      // elements on its left and next K
      // elements on its right
      function countElements(arr, n, k) {
        var s = [];
 
        var next_greater = new Array(n + 1).fill(n);
 
        // Iterate over the array
        for (var i = 0; i < n; i++) {
          if (s.length === 0) {
            s.push(i);
            continue;
          }
 
          // If the stack is not empty and
          // the element at the top of the
          // stack is smaller than arr[i]
          while (s.length !== 0 && arr[s[s.length - 1]] <
          arr[i]) {
            // Store the index of next
            // greater element
            next_greater[s[s.length - 1]] = i;
 
            // Pop the top element
            s.pop();
          }
 
          // Insert the current index
          s.push(i);
        }
 
        // Stores the count
        var count = 0;
        //min integer value
        var maxi = -2147483648;
 
        for (var i = 0; i < n; i++) {
          if (next_greater[i] - i > k && maxi < arr[i]) {
            maxi = Math.max(maxi, arr[i]);
            count++;
          }
        }
        return count;
      }
 
      // Driver Code
      var arr = [4, 2, 3, 6, 4, 3, 2];
      var K = 2;
      var n = arr.length;
 
      document.write(countElements(arr, n, K));
       
</script>

2

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)