[hot100] 739. Température quotidienne

739. Température quotidienne
Donner un tableau entier temperatures ,Indique la température quotidienne,Renvoie un tableau answer ,Parmi eux answer[i] Signifie pour i Oh, mon Dieu.,La prochaine température plus élevée apparaît quelques jours plus tard.Si la température ne monte pas après ça,Veuillez utiliser 0 Pour remplacer.

Entrée: temperatures = [73,74,75,71,69,72,76,73]
Produits: [1,1,4,2,1,1,0,0]

Compréhension du sujet：
Pour les entrées 73,Il a besoin Après une journée Jusqu'à ce que la température augmente,Le lendemain,,Augmentation de la température à 74 ,Donc le résultat correspondant est 1.

Pour les entrées 74,Il a besoin MéridienUn jour. Jusqu'à ce que la température augmente,Le troisième jour,,Augmentation de la température à 75 ,Donc le résultat correspondant est 1.

Pour les entrées 75,Il passe 1 Il a découvert que la température était 71,Pas plus que ça.,Continue d'attendre,Tout le temps J'ai attendu quatre jours.,Attendez que la température augmente le septième jour.,Augmentation de la température à 76 ,Donc le résultat correspondant est 4 .

Pour les entrées 71,Il passe 1 Il a découvert que la température était 69,Pas plus que ça.,Continue d'attendre,Tout le temps J'ai attendu deux jours.,Attendez que la température augmente le sixième jour.,Augmentation de la température à 72 ,Donc le résultat correspondant est 2 .

Pour les entrées 69,C'est Après une journée On a découvert que la température était 72, Déjà dépassé ,Donc le résultat correspondant est 1 .

Pour les entrées 72,C'est Après une journée On a découvert que la température était 76, Déjà dépassé ,Donc le résultat correspondant est 1 .

Pour les entrées 76,Suivi Pas de température Peut être dépassé ,Donc le résultat correspondant est 0 .

Pour les entrées 73,Suivi Pas de température Peut être dépassé ,Donc le résultat correspondant est 0 .

Des idées： Pour chaque valeur de température Faites une recherche en arrière , Trouver une valeur supérieure à la température actuelle ,C'est la façon la plus facile de penser.

Principes： Est de gauche à droite tous les autres nombres sauf le dernier sont traversés une fois , Le résultat correspondant à la dernière donnée doit être 0,Pas besoin de calculer..

En traversant, Chaque numéro va au dernier numéro , Jusqu'à ce qu'un plus grand nombre soit trouvé ,CompterNombre de fois Est la valeur de la sortie correspondante .

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        int len = temperatures.length;
        int[] res = new int[len];
        for(int i=0;i<len;i++){
    
            int cur = temperatures[i];
            if(cur < 100){
    
                for(int j=i+1;j<len;j++){
    
                    if(temperatures[j] > cur){
    
                        res[i] = j-i;
                        break;
                    }
                }
            }
        }
        return res;

    }

}

Résoudre avec la pile：
Pile décroissante ： Il n'y a que des éléments décroissants dans la pile .
Traverser tout le tableau,Si la pile n'est pas vide, Et le nombre actuel est supérieur à l'élément supérieur de la pile , Donc ce n'est pas Pile décroissante , Il faut donc enlever l'élément supérieur de la pile , Parce que le nombre actuel est plus grand que le nombre de l'élément supérieur de la pile , Et ça doit être le premier plus grand nombre que l'élément supérieur de la pile , Trouver directement l'écart d'indice est la distance entre les deux .

Continuez à regarder les nouveaux éléments du Haut de la pile , Jusqu'à ce que le nombre actuel soit inférieur ou égal à l'arrêt de l'élément supérieur de la pile , Puis mettez les nombres sur la pile , De cette façon, vous pouvez garder la pile décroissante tout le temps , Et la distance entre chaque nombre et le premier plus grand peut être calculée .

class Solution {
    
    public int[] dailyTemperatures(int[] T) {
    
        Stack<Integer> stack = new Stack<>();
        int length = T.length;
        int[] result = new int[length];

        for (int i = 0; i < length; i++) {
    
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
    
                int pre = stack.pop();
                result[pre] = i - pre;
            }
            stack.add(i);

        }
        return result;
    }

   
}