Comment utiliser la pile monotone en Java

1. Le prochain élément plus important

Description du problème

Explication détaillée des idées

Cette question utilise une solution plus violente.

Nous initialisons d'abord un tableau res avec la même longueur que nums pour stocker les résultats. Nous parcourons pour extraire les valeurs en nums et recherchons dans nums2 jusqu'à ce que nous trouvions nums2[j] == nums[i]. Nous partons ensuite de j de nums2 Puis parcourons pour trouver un tableau plus grand que nums[i] et le renvoyons s'il ne le trouve pas, il renverra -1.

Code et résultats

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}

2.

Description du problème

Explication détaillée de l'idée

Cette question utilise également une méthode relativement violente. Identique à la question précédente.

Double boucle, cette méthode a évidemment une complexité temporelle plus élevée. Une méthode avec une complexité temporelle moindre est également proposée ici.

Pile monotone

Ce que nous maintenons est un tableau d'espacement, qui est le tableau de résultats. Créez d'abord une pile et déterminez si la pile est vide, poussez-la directement vers la pile. comparez l'élément supérieur de la pile avec l'élément actuel. Si Si l'élément actuel est supérieur à l'élément actuel, la différence est placée dans le tableau de résultats correspondant et l'élément supérieur de la pile est sauté si l'élément actuel est plus petit que. le tableau de résultats, il est poussé sur la pile.

Voici un lien vers l'animation, c'est une bonne idée d'apprendre la pile monotone en animation.

Code et résultats

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

3. Le prochain élément plus important II

Description du problème

idée détaillée

L'idée de cette question est une pile monotone. La question 1 est craquée par force brute. . Cette question nécessite l'utilisation d'une pile monotone.

Le principe est le même que la méthode de la deuxième question, faites juste attention à la boucle. Accédez directement au code. Si vous ne le connaissez pas, vous pouvez regarder la vidéo de la deuxième question puis voir celle-ci.

Code et résultats

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {//最多循环一次，只需要2*n-1就够用了
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);//利用取模来进行循环也是一种常用的方法
        }
        return ret;
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!