El subarreglo más pequeño que contiene valores mínimos y máximos

Dada una array A de tamaño N. La tarea es encontrar la longitud del subarreglo más pequeño que contiene valores máximos y mínimos.
Ejemplos: 
 

Input : A[] = {1, 5, 9, 7, 1, 9, 4}
Output : 2
subarray {1, 9} has both maximum and minimum value.

Input : A[] = {2, 2, 2, 2}
Output : 1
2 is both maximum and minimum here.

Enfoque: La idea es utilizar la técnica de dos puntos aquí: 
 

• Encuentre los valores máximo y mínimo de la array.
• Recorra la array y almacene las últimas apariciones de valores máximos y mínimos.
• Si la última ocurrencia de máximo es pos_max y mínimo es pos_min , entonces el valor mínimo de abs(pos_min – pos_max) + 1 es nuestra respuesta requerida.

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

// C++ implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return length of
// smallest subarray containing both
// maximum and minimum value
int minSubarray(int A[], int n)
{
 
    // find maximum and minimum
    // values in the array
    int minValue = *min_element(A, A + n);
    int maxValue = *max_element(A, A + n);
 
    int pos_min = -1, pos_max = -1, ans = INT_MAX;
 
    // iterate over the array and set answer
    // to smallest difference between position
    // of maximum and position of minimum value
    for (int i = 0; i < n; i++) {
 
        // last occurrence of minValue
        if (A[i] == minValue)
            pos_min = i;
 
        // last occurrence of maxValue
        if (A[i] == maxValue)
            pos_max = i;
 
        if (pos_max != -1 and pos_min != -1)
            ans = min(ans, abs(pos_min - pos_max) + 1);
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int A[] = { 1, 5, 9, 7, 1, 9, 4 };
    int n = sizeof(A) / sizeof(A[0]);
 
    cout << minSubarray(A, n);
 
    return 0;
}

// Java implementation of above approach
import java.util.*;
 
class GFG
{
 
// Function to return length of
// smallest subarray containing both
// maximum and minimum value
static int minSubarray(int A[], int n)
{
 
    // find maximum and minimum
    // values in the array
    int minValue = A[0];
    for(int i = 1; i < n; i++)
    {
        if(A[i] < minValue)
            minValue = A[i];
    }
    int maxValue = A[0];
    for(int i = 1; i < n; i++)
    {
        if(A[i] > maxValue)
            maxValue = A[i];
    }
 
    int pos_min = -1, pos_max = -1,
        ans = Integer.MAX_VALUE;
 
    // iterate over the array and set answer
    // to smallest difference between position
    // of maximum and position of minimum value
    for (int i = 0; i < n; i++)
    {
 
        // last occurrence of minValue
        if (A[i] == minValue)
            pos_min = i;
 
        // last occurrence of maxValue
        if (A[i] == maxValue)
            pos_max = i;
 
        if (pos_max != -1 && pos_min != -1)
            ans = Math.min(ans,
                  Math.abs(pos_min - pos_max) + 1);
    }
 
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int A[] = { 1, 5, 9, 7, 1, 9, 4 };
    int n = A.length;
 
    System.out.println(minSubarray(A, n));
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python3 implementation of above approach
import sys
 
# Function to return length of smallest
# subarray containing both maximum and
# minimum value
def minSubarray(A, n):
 
    # find maximum and minimum
    # values in the array
    minValue = min(A)
    maxValue = max(A)
 
    pos_min, pos_max, ans = -1, -1, sys.maxsize
 
    # iterate over the array and set answer
    # to smallest difference between position
    # of maximum and position of minimum value
    for i in range(0, n):
         
        # last occurrence of minValue
        if A[i] == minValue:
            pos_min = i
 
        # last occurrence of maxValue
        if A[i] == maxValue:
            pos_max = i
 
        if pos_max != -1 and pos_min != -1 :
            ans = min(ans, abs(pos_min - pos_max) + 1)
 
    return ans
 
# Driver code
A = [ 1, 5, 9, 7, 1, 9, 4 ]
n = len(A)
 
print(minSubarray(A, n))
 
# This code is contributed
# by Saurabh_Shukla

// C# implementation of above approach
using System;
using System.Linq;
 
public class GFG{
     
 
 
// Function to return length of
// smallest subarray containing both
// maximum and minimum value
static int minSubarray(int []A, int n)
{
 
    // find maximum and minimum
    // values in the array
    int minValue = A.Min();
    int maxValue = A.Max();
 
    int pos_min = -1, pos_max = -1, ans = int.MaxValue;
 
    // iterate over the array and set answer
    // to smallest difference between position
    // of maximum and position of minimum value
    for (int i = 0; i < n; i++) {
 
        // last occurrence of minValue
        if (A[i] == minValue)
            pos_min = i;
 
        // last occurrence of maxValue
        if (A[i] == maxValue)
            pos_max = i;
 
        if (pos_max != -1 && pos_min != -1)
            ans = Math.Min(ans, Math.Abs(pos_min - pos_max) + 1);
    }
 
    return ans;
}
 
// Driver code
 
 
    static public void Main (){
            int []A = { 1, 5, 9, 7, 1, 9, 4 };
    int n = A.Length;
 
    Console.WriteLine(minSubarray(A, n));
    }
}
// This code is contributed by anuj_67..

<?php
// PHP implementation of above approach
 
// Function to return length of
// smallest subarray containing both
// maximum and minimum value
function minSubarray($A, $n)
{
 
    // find maximum and minimum
    // values in the array
    $minValue = min($A);
    $maxValue = max($A);
 
    $pos_min = -1;
    $pos_max = -1;
    $ans = PHP_INT_MAX;
 
    // iterate over the array and set answer
    // to smallest difference between position
    // of maximum and position of minimum value
    for ($i = 0; $i < $n; $i++)
    {
 
        // last occurrence of minValue
        if ($A[$i] == $minValue)
            $pos_min = $i;
 
        // last occurrence of maxValue
        if ($A[$i] == $maxValue)
            $pos_max = $i;
 
        if ($pos_max != -1 and $pos_min != -1)
            $ans = min($ans, abs($pos_min -
                                 $pos_max) + 1);
    }
 
    return $ans;
}
 
// Driver code
$A = array(1, 5, 9, 7, 1, 9, 4);
$n = sizeof($A);
 
echo minSubarray($A, $n);
 
// This code is contributed by Ryuga
?>

<script>
    // Javascript implementation of above approach
     
    // Function to return length of
    // smallest subarray containing both
    // maximum and minimum value
    function minSubarray(A, n)
    {
 
        // find maximum and minimum
        // values in the array
        let minValue = Number.MAX_VALUE;
        let maxValue = Number.MIN_VALUE;
        for (let i = 0; i < n; i++)
        {
            minValue = Math.min(minValue, A[i]);
            maxValue = Math.max(maxValue, A[i]);
        }
 
        let pos_min = -1, pos_max = -1, ans = Number.MAX_VALUE;
 
        // iterate over the array and set answer
        // to smallest difference between position
        // of maximum and position of minimum value
        for (let i = 0; i < n; i++) {
 
            // last occurrence of minValue
            if (A[i] == minValue)
                pos_min = i;
 
            // last occurrence of maxValue
            if (A[i] == maxValue)
                pos_max = i;
 
            if (pos_max != -1 && pos_min != -1)
                ans = Math.min(ans, Math.abs(pos_min - pos_max) + 1);
        }
 
        return ans;
    }
     
    let A = [ 1, 5, 9, 7, 1, 9, 4 ];
    let n = A.length;
   
    document.write(minSubarray(A, n));
 
</script>

2

Complejidad temporal: O(n)
Espacio auxiliar: O(1)