Recuento de diferencias distintas entre dos elementos máximos de cada subarreglo

Dada una array arr[] de tamaño N . La tarea es contar el número de diferencias únicas entre los dos elementos máximos de cada subarreglo de tamaño al menos 2 del arreglo dado.

Ejemplos:

Entrada: array[] = { 5, 1, 3 }, N = 3
Salida: 2
Explicación: Los subarreglos son {5, 1}, {5, 1, 3}, {1, 3}.
{5, 1} – Primer máximo = 5; Segundo máximo = 1; diferencia = (5 – 1) = 4
{5, 1, 3} – Primer máximo = 5; Segundo máximo = 3; diferencia = (5 – 3) = 2
{1, 3} – Primer máximo = 3; Segundo máximo = 1; diferencia = (3 – 1) = 2
Las diferencias de altura únicas son {4, 2} = 2

Entrada: array[] = {5, 2, 3, 8}, N = 4
Salida: 4
Explicación: Los subarreglos son: {5, 2}, {5, 2, 3}, {5, 2, 3, 8 }, {2, 3}, {2, 3, 8}, {3, 8}
{5, 2} – Primer máximo = 5; Segundo máximo = 2; diferencia = (5 – 2) = 3
{5, 2, 3} – Primer máximo = 5; Segundo máximo = 3; diferencia = (5 – 3) = 2
{5, 2, 3, 8} – Primer máximo = 8; Segundo máximo = 5; diferencia = (8 – 5) = 3
{2, 3} – Primer máximo = 3; Segundo máximo = 2; diferencia = (3 – 2) = 1
{2, 3, 8} – Primer máximo = 8; Segundo máximo = 3; diferencia = (8 – 3) = 5
{3,8} – Primer máximo = 8; Segundo máximo = 3; diferencia = (8 – 3) = 5
Las diferencias de altura únicas son {3, 2, 1, 5} = 4

Planteamiento: El problema se puede resolver en base a la siguiente observación. Solo se requieren el primero y el segundo máximo para cada subarreglo. Cuando otro elemento máximo entra en el subarreglo, los valores máximos deben actualizarse. El concepto de pila se utiliza para implementar esta observación. Siga los pasos a continuación para resolver este problema.

• Almacene el siguiente elemento mayor a la izquierda y el siguiente elemento mayor a la derecha de cada elemento de array en dos arrays.
• Encuentre la diferencia entre el siguiente elemento mayor a la izquierda y el elemento original en ese índice, y la diferencia entre el siguiente elemento mayor a la derecha y el elemento original en ese índice y guárdelo en un conjunto que contenga valores únicos.
• Imprimir el tamaño del conjunto

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to count the number
// of unique differences
int countUnique(vector<int>& arr, int n)
{
    
    // Arrays to store next greater
    // to the left and next greater
    // to the right for every arr[i]
    vector<int> ngl(n, 0);
    vector<int> ngr(n, 0);
    stack<int> st;
    set<int> s;
  
    // Loop to find next greater element
    // to the left of arr[i]
    ngl[0] = -1;
    st.push(arr[0]);
    for (int i = 1; i < n; i++) {
        while (st.size() > 0 && arr[i] > st.top()) {
            st.pop();
        }
        if (st.size() == 0) {
            ngl[i] = -1;
        }
        else {
            ngl[i] = st.top();
        }
        st.push(arr[i]);
    }
    while (st.size() > 0) {
        st.pop();
    }
  
    // Loop to find next greater element
    // to the left of arr[i]
    ngr[n - 1] = -1;
    st.push(arr[n - 1]);
    for (int i = n - 2; i >= 0; i--) {
        while (st.size() > 0 && arr[i] >= st.top()) {
            st.pop();
        }
        if (st.size() != 0) {
            ngr[i] = st.top();
        }
        else {
            ngr[i] = -1;
        }
        st.push(arr[i]);
    }
  
    for (int i = 0; i < n; i++) {
        if (ngl[i] != -1) {
            s.insert(ngl[i] - arr[i]);
        }
        if (ngr[i] != -1) {
            s.insert(ngr[i] - arr[i]);
        }
    }
  
    return s.size();
}
  
// Driver code
int main()
{
    int N = 4;
    vector<int> arr = { 5, 2, 3, 8 };
    cout << (countUnique(arr, N));
  
    return 0;
}
  
    // This code is contributed by rakeshsahni

// Java code to implement above approach
import java.io.*;
import java.util.*;
  
class GFG {
  
    // Function to count the number
    // of unique differences
    public static int countUnique(int arr[], int n)
    {
        // Arrays to store next greater 
        // to the left and next greater 
        // to the right for every arr[i]
        int[] ngl = new int[n];
        int[] ngr = new int[n];
        Stack<Integer> st = new Stack<>();
        HashSet<Integer> s = new HashSet<>();
          
        // Loop to find next greater element 
        // to the left of arr[i]
        ngl[0] = -1;
        st.push(arr[0]);
        for (int i = 1; i < n; i++) {
            while (st.size() > 0 && 
                   arr[i] > st.peek()) {
                st.pop();
            }
            if (st.size() == 0) {
                ngl[i] = -1;
            }
            else {
                ngl[i] = st.peek();
            }
            st.push(arr[i]);
        }
        while (st.size() > 0) {
            st.pop();
        }
          
        // Loop to find next greater element 
        // to the left of arr[i]
        ngr[n - 1] = -1;
        st.push(arr[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            while (st.size() > 0 && 
                   arr[i] >= st.peek()) {
                st.pop();
            }
            if (st.size() != 0) {
                ngr[i] = st.peek();
            }
            else {
                ngr[i] = -1;
            }
            st.push(arr[i]);
        }
          
        for (int i = 0; i < n; i++) {
            if (ngl[i] != -1) {
                s.add(ngl[i] - arr[i]);
            }
            if (ngr[i] != -1) {
                s.add(ngr[i] - arr[i]);
            }
        }
          
        return s.size();
    }
    
    // Driver code
    public static void main(String[] args)
    {
        int N = 4;
        int arr[] = { 5, 2, 3, 8 };
        System.out.println(countUnique(
          arr, N));
    }
}

# Python 3 code to implement above approach
  
# Function to count the number
# of unique differences
def countUnique(arr, n):
  
    # Arrays to store next greater
    # to the left and next greater
    # to the right for every arr[i]
    ngl = [0]*(n)
    ngr = [0]*(n)
    st = []
    s = set([])
  
    # Loop to find next greater element
    # to the left of arr[i]
    ngl[0] = -1
    st.append(arr[0])
    for i in range(1, n):
        while (len(st) > 0 and arr[i] > st[-1]):
            st.pop()
  
        if (len(st) == 0):
            ngl[i] = -1
  
        else:
            ngl[i] = st[-1]
  
        st.append(arr[i])
  
    while (len(st) > 0):
        st.pop()
  
    # Loop to find next greater element
    # to the left of arr[i]
    ngr[n - 1] = -1
    st.append(arr[n - 1])
    for i in range(n - 2, -1, -1):
        while (len(st) > 0 and arr[i] >= st[-1]):
            st.pop()
  
        if (len(st) != 0):
            ngr[i] = st[-1]
  
        else:
            ngr[i] = -1
  
        st.append(arr[i])
  
    for i in range(n):
        if (ngl[i] != -1):
            s.add(ngl[i] - arr[i])
  
        if (ngr[i] != -1):
            s.add(ngr[i] - arr[i])
  
    return len(s)
  
# Driver code
if __name__ == "__main__":
  
    N = 4
    arr = [5, 2, 3, 8]
    print(countUnique(arr, N))
  
    # This code is contributed by ukasp.

// C# code to implement above approach
using System;
using System.Collections.Generic;
  
class GFG {
  
  // Function to count the number
  // of unique differences
  public static int countUnique(int[] arr, int n)
  {
    // Arrays to store next greater 
    // to the left and next greater 
    // to the right for every arr[i]
    int[] ngl = new int[n];
    int[] ngr = new int[n];
    Stack<int> st = new Stack<int>();
    HashSet<int> s = new HashSet<int>();
  
    // Loop to find next greater element 
    // to the left of arr[i]
    ngl[0] = -1;
    st.Push(arr[0]);
    for (int i = 1; i < n; i++) {
      while (st.Count > 0 && 
             arr[i] > st.Peek()) {
        st.Pop();
      }
      if (st.Count == 0) {
        ngl[i] = -1;
      }
      else {
        ngl[i] = st.Peek();
      }
      st.Push(arr[i]);
    }
    while (st.Count > 0) {
      st.Pop();
    }
  
    // Loop to find next greater element 
    // to the left of arr[i]
    ngr[n - 1] = -1;
    st.Push(arr[n - 1]);
    for (int i = n - 2; i >= 0; i--) {
      while (st.Count > 0 && 
             arr[i] >= st.Peek()) {
        st.Pop();
      }
      if (st.Count != 0) {
        ngr[i] = st.Peek();
      }
      else {
        ngr[i] = -1;
      }
      st.Push(arr[i]);
    }
  
    for (int i = 0; i < n; i++) {
      if (ngl[i] != -1) {
        s.Add(ngl[i] - arr[i]);
      }
      if (ngr[i] != -1) {
        s.Add(ngr[i] - arr[i]);
      }
    }
  
    return s.Count;
  }
  
  // Driver code
  public static void Main()
  {
    int N = 4;
    int[] arr = { 5, 2, 3, 8 };
    Console.Write(countUnique(arr, N));
  }
}
  
// This code is contributed by saurabh_jaiswal.

<script>
    // JavaScript code for the above approach
  
    // Function to count the number
    // of unique differences
    function countUnique(arr, n) {
  
      // Arrays to store next greater
      // to the left and next greater
      // to the right for every arr[i]
      let ngl = new Array(n).fill(0);
      let ngr = new Array(n).fill(0);
      let st = [];
      let s = new Set();
  
      // Loop to find next greater element
      // to the left of arr[i]
      ngl[0] = -1;
      st.push(arr[0]);
      for (let i = 1; i < n; i++) {
        while (st.length > 0 && arr[i] > st[st.length - 1]) {
          st.pop();
        }
        if (st.length == 0) {
          ngl[i] = -1;
        }
        else {
          ngl[i] = st[st.length - 1];
        }
        st.push(arr[i]);
      }
      while (st.length > 0) {
        st.pop();
      }
  
      // Loop to find next greater element
      // to the left of arr[i]
      ngr[n - 1] = -1;
      st.push(arr[n - 1]);
      for (let i = n - 2; i >= 0; i--) {
        while (st.length > 0 && arr[i] >= st[st.length - 1]) {
          st.pop();
        }
        if (st.length != 0) {
          ngr[i] = st[st.length - 1];
        }
        else {
          ngr[i] = -1;
        }
        st.push(arr[i]);
      }
  
      for (let i = 0; i < n; i++) {
        if (ngl[i] != -1) {
          s.add(ngl[i] - arr[i]);
        }
        if (ngr[i] != -1) {
          s.add(ngr[i] - arr[i]);
        }
      }
  
      return s.size;
    }
  
    // Driver code
    let N = 4;
    let arr = [5, 2, 3, 8];
    document.write(countUnique(arr, N));
  
  // This code is contributed by Potta Lokesh
  </script>

4

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