Número de subarreglos cuyo mínimo y máximo son iguales

Dada una array de n enteros, encuentre el número de subarreglos cuyos elementos mínimo y máximo sean iguales. Un subarreglo se define como una secuencia no vacía de elementos consecutivos.

Ejemplos:  

Entrada: 2 3 1 1 
Salida: 5
Explicación: Los subarreglos son (2), (3), (1), (1) y (1, 1) 

Entrada: 2 4 5 3 3 3
Salida: 9
Explicación: Los subarreglos son (2), (4), (5), (3), (3, 3), (3, 3, 3), (3), (3, 3) y (3) 

Lo primero que hay que observar es que solo aquellos subarreglos cuyos elementos sean todos iguales tendrán el mismo mínimo y máximo. Tener diferentes elementos claramente significa diferentes mínimos y máximos. Por lo tanto, solo necesitamos calcular el número de elementos iguales continuos (por ejemplo, d) , luego, mediante la fórmula de combinaciones, obtenemos que el número de subarreglos es:

No de subarreglos posibles con d elementos = (d * (d+1) / 2) 
donde d es un número de elementos iguales continuos. 

Atravesamos de 1-n y luego de I+1 a n y luego encontramos el número de elementos iguales continuos y luego agregamos al resultado los subarreglos posibles. 

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

// CPP program to count number of subarrays
// having same minimum and maximum.
#include <bits/stdc++.h>
using namespace std;
 
// calculate the no of contiguous subarrays
// which has same minimum and maximum
int calculate(int a[], int n)
{
    // stores the answer
    int ans = 0;
 
    // loop to traverse from 0-n
    for (int i = 0; i < n; i++) {
 
        // start checking subarray from next element
        int r = i + 1;
 
        // traverse for finding subarrays
        for (int j = r; j < n; j++) {
 
            // if the elements are same then
            // we check further and keep a count
            // of same numbers in 'r'
            if (a[i] == a[j])
                r += 1;
            else
                break;
        }
 
        // the no of elements in between r and i
        // with same elements.
        int d = r - i;
 
        // the no of subarrays that can be formed
        // between i and r
        ans += (d * (d + 1) / 2);
 
        // again start checking from the next index
        i = r - 1;
    }
 
    // returns answer
    return ans;
}
 
// drive program to test the above function
int main()
{
    int a[] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << calculate(a, n);
    return 0;
}

// Java program to count number of subarrays
// having same minimum and maximum.
 
class Subarray
{
    // calculate the no of contiguous subarrays
    // which has same minimum and maximum
    static int calculate(int a[], int n)
    {
        // stores the answer
        int ans = 0;
 
        // loop to traverse from 0-n
        for (int i = 0; i < n; i++) {
 
            // start checking subarray from
            // next element
            int r = i + 1;
 
            // traverse for finding subarrays
            for (int j = r; j < n; j++) {
 
                // if the elements are same then
                // we check further and keep a
                // count of same numbers in 'r'
                if (a[i] == a[j])
                    r += 1;
                else
                    break;
            }
 
            // the no of elements in between r
            // and i with same elements.
            int d = r - i;
 
            // the no. of subarrays that can be
            // formed between i and r
            ans += (d * (d + 1) / 2);
 
            // again start checking from the next
            // index
            i = r - 1;
        }
 
        // returns answer
        return ans;
    }
     
    // Driver program to test above functions
    public static void main(String[] args)
    {
    int a[] = {  2, 4, 5, 3, 3, 3 };
    System.out.println(calculate(a, a.length));
    }
}
// This code is contributed by Prerna Saini

# Python3 program to count
# number of subarrays having
# same minimum and maximum.
 
# calculate the no of contiguous
# subarrays which has same
# minimum and maximum
def calculate(a, n):
     
    # stores the answer
    ans = 0;
    i = 0;
 
    # loop to traverse from 0-n
    while(i < n):
         
        # start checking subarray
        # from next element
        r = i + 1;
 
        # traverse for
        # finding subarrays
        for j in range(r, n):
             
            # if the elements are same
            # then we check further
            # and keep a count of same
            # numbers in 'r'
            if (a[i] == a[j]):
                r = r + 1;
            else:
                break;
 
        # the no of elements in
        # between r and i with
        # same elements.
        d = r - i;
 
        # the no of subarrays that
        # can be formed between i and r
        ans = ans + (d * (d + 1) / 2);
 
        # again start checking
        # from the next index
        i = r - 1;
        i = i + 1;
 
    # returns answer
    return int(ans);
 
# Driver Code
a = [ 2, 4, 5, 3, 3, 3 ];
n = len(a);
print(calculate(a, n));
 
# This code is contributed by mits

// Program to count number
// of subarrays having same
// minimum and maximum.
using System;
 
class Subarray {
    // calculate the no of contiguous
    // subarrays which has the same
    // minimum and maximum
    static int calculate(int[] a, int n)
    {
        // stores the answer
        int ans = 0;
 
        // loop to traverse from 0-n
        for (int i = 0; i < n; i++) {
 
            // start checking subarray
            // from next element
            int r = i + 1;
 
            // traverse for finding subarrays
            for (int j = r; j < n; j++) {
 
                // if the elements are same then
                // we check further and keep a
                // count of same numbers in 'r'
                if (a[i] == a[j])
                    r += 1;
                else
                    break;
            }
 
            // the no of elements in between
            // r and i with same elements.
            int d = r - i;
 
            // the no. of subarrays that can
            // be formed between i and r
            ans += (d * (d + 1) / 2);
 
            // again start checking from
            // the next index
            i = r - 1;
        }
 
        // returns answer
        return ans;
    }
 
    // Driver program
    public static void Main()
    {
        int[] a = { 2, 4, 5, 3, 3, 3 };
        Console.WriteLine(calculate(a, a.Length));
    }
}
 
// This code is contributed by Anant Agarwal.

<?php
// PHP program to count number
// of subarrays having same
// minimum and maximum.
 
// calculate the no of contiguous
// subarrays which has same minimum
// and maximum
function calculate($a, $n)
{
    // stores the answer
    $ans = 0;
 
    // loop to traverse from 0-n
    for ($i = 0; $i < $n; $i++)
    {
 
        // start checking subarray
        // from next element
        $r = $i + 1;
 
        // traverse for finding subarrays
        for ($j = $r; $j < $n; $j++)
        {
 
            // if the elements are same
            // then we check further and
            // keep a count of same numbers
            // in 'r'
            if ($a[$i] == $a[$j])
                $r += 1;
            else
                break;
        }
 
        // the no of elements in between
        //  r and i with same elements.
        $d = $r - $i;
 
        // the no of subarrays that
        // can be formed between i and r
        $ans += ($d * ($d + 1) / 2);
 
        // again start checking
        // from the next index
        $i = $r - 1;
    }
 
    // returns answer
    return $ans;
}
 
// Driver Code
$a = array( 2, 4, 5, 3, 3, 3 );
$n = count($a);
echo calculate($a, $n);
 
// This code is contributed by Sam007
?>

<script>
// JavaScript program to count number of subarrays
// having same minimum and maximum.
 
 
    // calculate the no of contiguous subarrays
    // which has same minimum and maximum
    function calculate(a, n)
    {
        // stores the answer
        let ans = 0;
 
        // loop to traverse from 0-n
        for (let i = 0; i < n; i++) {
 
            // start checking subarray from
            // next element
            let r = i + 1;
 
            // traverse for finding subarrays
            for (let j = r; j < n; j++) {
 
                // if the elements are same then
                // we check further and keep a
                // count of same numbers in 'r'
                if (a[i] == a[j])
                    r += 1;
                else
                    break;
            }
 
            // the no of elements in between r
            // and i with same elements.
            let d = r - i;
 
            // the no. of subarrays that can be
            // formed between i and r
            ans += (d * (d + 1) / 2);
 
            // again start checking from the next
            // index
            i = r - 1;
        }
 
        // returns answer
        return ans;
    }
 
// Driver Code
 
    let a = [ 2, 4, 5, 3, 3, 3 ];
    document.write(calculate(a, a.length));
         
</script>

9

Complejidad de tiempo: O(n) , donde n es el tamaño de la array dada.
Espacio Auxiliar: O(1) 

Este artículo es una contribución de Raja Vikramaditya (Raj) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.