Recuento de elementos que son el segundo más pequeño entre tres elementos consecutivos

Dada una permutación P de primeros N números naturales. La tarea es encontrar el número de elementos P _i tal que P _i sea el segundo más pequeño entre P _{i – 1} , P _i y P _{i + 1} .
Ejemplos: 
 

Entrada: P[] = {2, 5, 1, 3, 4} 
Salida: 1 
3 es el único elemento de este tipo.
Entrada: P[] = {1, 2, 3, 4} 
Salida: 2 
 

Enfoque: Atraviese la permutación de 1 a N – 2 (indexación basada en cero) y verifique las dos condiciones a continuación. Si alguna de estas condiciones satisface, entonces incremente la respuesta requerida. 
 

• Si P[i – 1] < P[i] < P[i + 1] .
• Si P[i – 1] > P[i] > P[i + 1] .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of elements
// P[i] such that P[i] is the second smallest
// among P[i – 1], P[i] and P[i + 1]
int countElements(int p[], int n)
{
    // To store the required answer
    int ans = 0;
 
    // Traverse from the second element
    // to the second last element
    for (int i = 1; i < n - 1; i++) {
        if (p[i - 1] > p[i] and p[i] > p[i + 1])
            ans++;
        else if (p[i - 1] < p[i] and p[i] < p[i + 1])
            ans++;
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int p[] = { 2, 5, 1, 3, 4 };
    int n = sizeof(p) / sizeof(p[0]);
 
    cout << countElements(p, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the count of elements
// P[i] such that P[i] is the second smallest
// among P[i-1], P[i] and P[i + 1]
static int countElements(int p[], int n)
{
    // To store the required answer
    int ans = 0;
 
    // Traverse from the second element
    // to the second last element
    for (int i = 1; i < n - 1; i++)
    {
        if (p[i - 1] > p[i] && p[i] > p[i + 1])
            ans++;
        else if (p[i - 1] < p[i] && p[i] < p[i + 1])
            ans++;
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void main(String []args)
{
    int p[] = { 2, 5, 1, 3, 4 };
    int n = p.length;
 
    System.out.println(countElements(p, n));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Function to return the count of elements
# P[i] such that P[i] is the second smallest
# among P[i – 1], P[i] and P[i + 1]
def countElements(p, n) :
 
    # To store the required answer
    ans = 0;
 
    # Traverse from the second element
    # to the second last element
    for i in range(1, n - 1) :
         
        if (p[i - 1] > p[i] and p[i] > p[i + 1]) :
            ans += 1;
        elif (p[i - 1] < p[i] and p[i] < p[i + 1]) :
            ans += 1;
     
    # Return the required answer
    return ans;
 
# Driver code
if __name__ == "__main__" :
 
    p = [ 2, 5, 1, 3, 4 ];
    n = len(p);
 
    print(countElements(p, n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count of elements
// P[i] such that P[i] is the second smallest
// among P[i-1], P[i] and P[i + 1]
static int countElements(int []p, int n)
{
    // To store the required answer
    int ans = 0;
 
    // Traverse from the second element
    // to the second last element
    for (int i = 1; i < n - 1; i++)
    {
        if (p[i - 1] > p[i] && p[i] > p[i + 1])
            ans++;
        else if (p[i - 1] < p[i] && p[i] < p[i + 1])
            ans++;
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    int []p = { 2, 5, 1, 3, 4 };
    int n = p.Length;
 
    Console.WriteLine(countElements(p, n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the approach
 
// Function to return the count of elements
// P[i] such that P[i] is the second smallest
// among P[i-1], P[i] and P[i + 1]
    function countElements(p , n)
    {
        // To store the required answer
        var ans = 0;
 
        // Traverse from the second element
        // to the second last element
        for (i = 1; i < n - 1; i++) {
            if (p[i - 1] > p[i] && p[i] > p[i + 1])
                ans++;
            else if (p[i - 1] < p[i] && p[i] < p[i + 1])
                ans++;
        }
 
        // Return the required answer
        return ans;
    }
 
    // Driver code
     
        var p = [ 2, 5, 1, 3, 4 ];
        var n = p.length;
 
        document.write(countElements(p, n));
 
// This code contributed by Rajput-Ji
 
</script>

1

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)