Número esperado de grupos de automóviles formados en el camino infinito

Dada una array speed[] de tamaño N que denota la velocidad de N automóviles que se mueven en una carretera de un solo carril infinitamente larga (es decir, no se permite adelantar) de izquierda a derecha . Inicialmente, el automóvil más a la derecha está en la primera posición y cada vez que un automóvil con mayor velocidad alcanza un automóvil con menor velocidad, comienzan a moverse con la velocidad hacia el automóvil más lento y forman un grupo. La tarea es encontrar el número total de grupos que se formarán.

Nota: Un solo automóvil también se considera un grupo.

Ejemplos:

Entrada: velocidad[] = {1, 4, 5, 2, 17, 4 }
Salida: 3
Explicación: Después de cierto tiempo, el automóvil con velocidad 17 llegará al automóvil con velocidad 4 (automóvil 5) y formará un grupo. 
Y de manera similar, los autos con velocidad 4 y 5 comenzarán a moverse con velocidad 2 al llegar al auto3.
Los grupos serán (coche0), (coche1, coche2, coche3), (coche4, coche5).

Entrada: velocidad[] = {2, 3, 4, 7, 7}
Salida: 5
Explicación: Cada automóvil formará un grupo.

Enfoque: La solución se basa en el enfoque codicioso . Aquí, un automóvil con menos velocidad forma un grupo con todos los automóviles detrás de él y tiene velocidades mayores que él mismo. Siga los pasos a continuación para resolver el problema:

1. Comience a iterar desde el último índice de la array speed[].
2. Almacene la velocidad del automóvil en una variable, digamos currentCar .
3. Se forma un grupo hasta que la velocidad de los autos detrás del auto actual es mayor que él mismo. Por lo tanto, aumente el valor de los grupos tan pronto como se encuentre un automóvil con menos velocidad detrás de él o cuando la array esté fuera de los límites.

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

// C++ code to implement above approach
#include <bits/stdc++.h>
#include <vector>
using namespace std;
 
// Function to count total number of clusters
int countClusters(vector<int>& speed)
{
    int N = speed.size();
     
    // For number of clusters
    int cluster = 0;
 
    for (int i = N - 1; i >= 0; i--) {
        int currentCar = speed[i];
         
        // comparing with previous car
        while (i != 0 and speed[i - 1]
               > currentCar) {
            i--;
        }
        cluster++;
    }
    return cluster;
}
 
// Driver code
int main()
{
    vector<int> speed = { 1, 4, 5, 2, 17, 4 };
    int clusters = countClusters(speed);
    cout << clusters;
    return 0;
}

// Java program to implement
// the above approach
class GFG
{
 
  // Function to count total number of clusters
  static int countClusters(int []speed)
  {
    int N = speed.length;
 
    // For number of clusters
    int cluster = 0;
 
    for (int i = N - 1; i >= 0; i--) {
      int currentCar = speed[i];
 
      // comparing with previous car
      while (i != 0 && speed[i - 1]
             > currentCar) {
        i--;
      }
      cluster++;
    }
    return cluster;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int []speed = { 1, 4, 5, 2, 17, 4 };
    int clusters = countClusters(speed);
    System.out.println(clusters);
 
  }
}
 
// This code is contributed by Saurabh Jaiswal

# Python code to implement above approach
 
# Function to count total number of clusters
def countClusters(speed):
    N = len(speed)
    clusters = 0
    i = N-1
    while(i >= 0):
        currentCar = speed[i]
        while(i != 0 and speed[i-1] > currentCar):
            i = i-1
        clusters = clusters+1
        i = i-1
    return clusters
 
# Driver code
if __name__ == '__main__':
    speed = [1, 4, 5, 2, 17, 4]
    clusters = countClusters(speed)
    print(clusters)

// C# program to implement
// the above approach
using System;
class GFG
{
 
  // Function to count total number of clusters
  static int countClusters(int []speed)
  {
    int N = speed.Length;
 
    // For number of clusters
    int cluster = 0;
 
    for (int i = N - 1; i >= 0; i--) {
      int currentCar = speed[i];
 
      // comparing with previous car
      while (i != 0 && speed[i - 1]
             > currentCar) {
        i--;
      }
      cluster++;
    }
    return cluster;
  }
 
  // Driver Code
  public static void Main()
  {
    int []speed = { 1, 4, 5, 2, 17, 4 };
    int clusters = countClusters(speed);
    Console.Write(clusters);
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to count total number of clusters
       function countClusters(speed) {
           let N = speed.length;
 
           // For number of clusters
           let cluster = 0;
 
           for (let i = N - 1; i >= 0; i--) {
               let currentCar = speed[i];
 
               // comparing with previous car
               while (i != 0 && speed[i - 1]
                   > currentCar) {
                   i--;
               }
               cluster++;
           }
           return cluster;
       }
 
       // Driver code
 
       let speed = [1, 4, 5, 2, 17, 4];
       let clusters = countClusters(speed);
       document.write(clusters);
 
 // This code is contributed by Potta Lokesh
   </script>

3

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