Recuento de días que faltan para el día siguiente con temperatura más alta

Dada una lista arr[] de temperaturas diarias. Para cada día, la tarea es encontrar la cantidad de días que quedan para el próximo día con temperaturas más cálidas. Si no hay tal día para el cual sea posible una temperatura más cálida, imprima -1 .
Ejemplos:

Entrada: arr[] = {73, 74, 75, 71, 69, 72, 76, 73} 
Salida: {1, 1, 4, 2, 1, 1, -1, -1} 
Explicación: 
Para temperatura 73, la siguiente temperatura más cálida es 74, que está a una distancia 1 
Para la temperatura 74, la siguiente temperatura más cálida es 75, que está a una distancia 1 
Para la temperatura 75, la siguiente temperatura más cálida es 76, que está a una distancia 4 
Para la temperatura 71, la siguiente temperatura más cálida es 72, que está a una distancia distancia 2 
Para la temperatura 69, la siguiente temperatura más cálida es 72, que está a una distancia 1 
Para la temperatura 72, la siguiente temperatura más cálida es 76, que está a una distancia 1 
Para la temperatura 76, no hay un próximo día más cálido válido 
Para la temperatura 73, no hay un próximo día válido día más cálido
Entrada:array[] = {75, 74, 73, 72} 
Salida: {-1, -1, -1, -1}

Enfoque ingenuo: la idea es iterar para cada posible par de la array y verificar las siguientes temperaturas más altas para cada elemento actual.
Complejidad de tiempo: O(N ² ) 
Espacio auxiliar: O(1)
Enfoque eficiente: Este problema básicamente pide encontrar qué tan lejos está el índice actual del índice de la siguiente temperatura mayor a la temperatura en el índice actual. La forma más óptima de resolver este problema es haciendo uso de una pila . A continuación se muestran los pasos:

1. Iterar sobre la temperatura diaria de la array dada arr[] usando el índice actual.
2. Si la pila está vacía, inserte el índice actual en la pila.
3. Si la pila no está vacía, haga lo siguiente: 
   • Si la temperatura en el índice actual es menor que la temperatura del índice en la parte superior de la pila, empuje el índice actual.
   • Si la temperatura en el índice actual es mayor que la temperatura del índice en la parte superior de la pila, actualice el número de días para esperar una temperatura más cálida como:

 
 

índice actual: índice en la parte superior de la pila

 

• Haga estallar la pila una vez que se haya actualizado el número de días en la lista de salida.

1. Repita los pasos anteriores para todos los índices de la pila que sean menores que la temperatura en el índice actual.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to determine how many days
// required to wait for the next
// warmer temperature
void dailyTemperatures(vector<int>& T)
{
    int n = T.size();
 
    // To store the answer
    vector<int> daysOfWait(n, -1);
    stack<int> s;
 
    // Traverse all the temperatures
    for (int i = 0; i < n; i++) {
 
        // Check if current index is the
        // next warmer temperature of
        // any previous indexes
        while (!s.empty()
               && T[s.top()] < T[i]) {
 
            daysOfWait[s.top()]
                = i - s.top();
 
            // Pop the element
            s.pop();
        }
 
        // Push the current index
        s.push(i);
    }
 
    // Print waiting days
    for (int i = 0; i < n; i++) {
        cout << daysOfWait[i] << " ";
    }
}
 
// Driver Code
int main()
{
    // Given temperatures
    vector<int> arr{ 73, 74, 75, 71,
                     69, 72, 76, 73 };
 
    // Function Call
    dailyTemperatures(arr);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
 
// Function to determine how many days
// required to wait for the next
// warmer temperature
static void dailyTemperatures(int[] T)
{
    int n = T.length;
 
    // To store the answer
    int[] daysOfWait = new int[n];
    Arrays.fill(daysOfWait, -1);
     
    Stack<Integer> s = new Stack<>();
 
    // Traverse all the temperatures
    for(int i = 0; i < n; i++)
    {
         
        // Check if current index is the
        // next warmer temperature of
        // any previous indexes
        while (!s.isEmpty() && T[s.peek()] < T[i])
        {
            daysOfWait[s.peek()] = i - s.peek();
             
            // Pop the element
            s.pop();
        }
         
        // Push the current index
        s.push(i);
    }
 
    // Print waiting days
    for(int i = 0; i < n; i++)
    {
        System.out.print(daysOfWait[i] + " ");
    }
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given temperatures
    int[] arr = { 73, 74, 75, 71,
                  69, 72, 76, 73 };
     
    // Function call
    dailyTemperatures(arr);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function to determine how many days
# required to wait for the next
# warmer temperature
def dailyTemperatures(T):
 
    n = len(T)
 
    # To store the answer
    daysOfWait = [-1] * n
    s = []
 
    # Traverse all the temperatures
    for i in range(n):
 
        # Check if current index is the
        # next warmer temperature of
        # any previous indexes
        while(len(s) != 0 and
              T[s[-1]] < T[i]):
            daysOfWait[s[-1]] = i - s[-1]
 
            # Pop the element
            s.pop(-1)
 
        # Push the current index
        s.append(i)
 
    # Print waiting days
    for i in range(n):
        print(daysOfWait[i], end = " ")
 
# Driver Code
 
# Given temperatures
arr = [ 73, 74, 75, 71,
        69, 72, 76, 73 ]
 
# Function call
dailyTemperatures(arr)
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to determine how many days
// required to wait for the next
// warmer temperature
static void dailyTemperatures(int[] T)
{
    int n = T.Length;
 
    // To store the answer
    int[] daysOfWait = new int[n];
    for(int i = 0; i < n; i++)
        daysOfWait[i] = -1;
     
    Stack<int> s = new Stack<int>();
 
    // Traverse all the temperatures
    for(int i = 0; i < n; i++)
    {
         
        // Check if current index is the
        // next warmer temperature of
        // any previous indexes
        while (s.Count != 0 && T[s.Peek()] < T[i])
        {
            daysOfWait[s.Peek()] = i - s.Peek();
             
            // Pop the element
            s.Pop();
        }
         
        // Push the current index
        s.Push(i);
    }
 
    // Print waiting days
    for(int i = 0; i < n; i++)
    {
        Console.Write(daysOfWait[i] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given temperatures
    int[] arr = { 73, 74, 75, 71,
                  69, 72, 76, 73 };
     
    // Function call
    dailyTemperatures(arr);
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
 
// JavaScript program for the above approach
 
// Function to determine how many days
// required to wait for the next
// warmer temperature
function dailyTemperatures(T)
{
    var n = T.length;
 
    // To store the answer
    var daysOfWait = Array(n).fill(-1);
    var s = [];
 
    // Traverse all the temperatures
    for (var i = 0; i < n; i++) {
 
        // Check if current index is the
        // next warmer temperature of
        // any previous indexes
        while (s.length!=0
               && T[s[s.length-1]] < T[i]) {
 
            daysOfWait[s[s.length-1]]
                = i - s[s.length-1];
 
            // Pop the element
            s.pop();
        }
 
        // Push the current index
        s.push(i);
    }
 
    // Print waiting days
    for (var i = 0; i < n; i++) {
        document.write( daysOfWait[i] + " ");
    }
}
 
// Driver Code
// Given temperatures
var arr = [73, 74, 75, 71,
                 69, 72, 76, 73 ];
// Function Call
dailyTemperatures(arr);
 
 
</script>

1 1 4 2 1 1 -1 -1

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