Número de subarreglos no decrecientes de longitud K

Dada una array arr[] de longitud N , la tarea es encontrar el número de subarreglos no decrecientes de longitud K.
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, 2, 5}, K = 2 
Salida: 3 
{1, 2}, {2, 3} y {2, 5} son los 
subarreglos crecientes de longitud 2.
Entrada : arr[] = {1, 2, 3, 2, 5}, K = 1 
Salida: 5 
 

Enfoque ingenuo Genere todos los subconjuntos de longitud K y luego verifique si el subconjunto cumple la condición. Por lo tanto, la complejidad temporal del enfoque será O(N * K) .
Mejor enfoque: un mejor enfoque será utilizar la técnica de dos puntos . Digamos que el índice actual es i . 
 

• Encuentre el mayor índice j , tal que el subarreglo arr[i…j] no sea decreciente. Esto se puede lograr simplemente incrementando el valor de j a partir de i + 1 y verificando si arr[j] es mayor que arr[j – 1] .
• Digamos que la longitud del subarreglo encontrado en el paso anterior es L . El número de subarreglos de longitud K contenidos en él será max(L – K + 1, 0) .
• Ahora, actualice i = j y repita los pasos anteriores mientras i está en el rango de índice.

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
// increasing subarrays of length k
int cntSubArrays(int* arr, int n, int k)
{
    // To store the final result
    int res = 0;
 
    int i = 0;
    // Two pointer loop
    while (i < n) {
 
        // Initialising j
        int j = i + 1;
 
        // Looping till the subarray increases
        while (j < n and arr[j] >= arr[j - 1])
            j++;
 
        // Updating the required count
        res += max(j - i - k + 1, 0);
 
        // Updating i
        i = j;
    }
 
    // Returning res
    return res;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 2, 5 };
    int n = sizeof(arr) / sizeof(int);
    int k = 2;
 
    cout << cntSubArrays(arr, n, k);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the count of
// increasing subarrays of length k
static int cntSubArrays(int []arr, int n, int k)
{
    // To store the final result
    int res = 0;
 
    int i = 0;
     
    // Two pointer loop
    while (i < n)
    {
 
        // Initialising j
        int j = i + 1;
 
        // Looping till the subarray increases
        while (j < n && arr[j] >= arr[j - 1])
            j++;
 
        // Updating the required count
        res += Math.max(j - i - k + 1, 0);
 
        // Updating i
        i = j;
    }
 
    // Returning res
    return res;
}
 
// Driver code
public static void main(String []args)
{
    int arr[] = { 1, 2, 3, 2, 5 };
    int n = arr.length;
    int k = 2;
 
    System.out.println(cntSubArrays(arr, n, k));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Function to return the count of
# increasing subarrays of length k
def cntSubArrays(arr, n, k) :
 
    # To store the final result
    res = 0;
 
    i = 0;
     
    # Two pointer loop
    while (i < n) :
 
        # Initialising j
        j = i + 1;
 
        # Looping till the subarray increases
        while (j < n and arr[j] >= arr[j - 1]) :
            j += 1;
 
        # Updating the required count
        res += max(j - i - k + 1, 0);
 
        # Updating i
        i = j;
 
    # Returning res
    return res;
 
# Driver code
if __name__ == "__main__" :
     
    arr = [ 1, 2, 3, 2, 5 ];
    n = len(arr);
    k = 2;
 
    print(cntSubArrays(arr, n, k));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to return the count of
// increasing subarrays of length k
static int cntSubArrays(int []arr, int n, int k)
{
    // To store the final result
    int res = 0;
 
    int i = 0;
     
    // Two pointer loop
    while (i < n)
    {
 
        // Initialising j
        int j = i + 1;
 
        // Looping till the subarray increases
        while (j < n && arr[j] >= arr[j - 1])
            j++;
 
        // Updating the required count
        res += Math.Max(j - i - k + 1, 0);
 
        // Updating i
        i = j;
    }
 
    // Returning res
    return res;
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 1, 2, 3, 2, 5 };
    int n = arr.Length;
    int k = 2;
 
    Console.WriteLine(cntSubArrays(arr, n, k));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of the approach
 
// Function to return the count of
// increasing subarrays of length k
function cntSubArrays(arr, n, k)
{
    // To store the final result
    var res = 0;
 
    var i = 0;
    // Two pointer loop
    while (i < n) {
 
        // Initialising j
        var j = i + 1;
 
        // Looping till the subarray increases
        while (j < n && arr[j] >= arr[j - 1])
            j++;
 
        // Updating the required count
        res += Math.max(j - i - k + 1, 0);
 
        // Updating i
        i = j;
    }
 
    // Returning res
    return res;
}
 
// Driver code
var arr = [ 1, 2, 3, 2, 5 ];
var n = arr.length;
var k = 2;
document.write( cntSubArrays(arr, n, k));
 
</script>

3

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