Supprimer les lettres dupliquées [avidité + pile monotone (maintenir la séquence monotone avec un tableau + Len)]

Préface

Quand il s'agit d'un problème de mots,La plupart impliquent des algorithmes gourmands,Cette situation,Pour comprendre le processus de cupidité,Ensuite, il est incorporé dans le Code.
Quand il s'agit d'ordre relatif/Les tailles avant et arrière,En général, la pile monotone est nécessaire pour la maintenance,Scénario commun：Retour en arrière par rapport au retour en arrière.
Pour la pile monotone/hashQuelque chose comme ça.,Une situation où un tableau peut être utilisé,On peut toujours utiliser un tableau,InJVMNiveau,En effetAPILes couches sont beaucoup plus rapides.,Et simple et léger.

Un.、Supprimer les lettres en double

2.、Avidité+Pile monotone

1、stack

// Supprimer la chaîne dupliquée
public class RemoveDuplicateLetters {
    
    /* target：Supprimer les lettres en double,L'ordre minimal du dictionnaire qui doit renvoyer les résultats est. Quands[i] >= s[i+1]Ets[i]Il y a beaucoup de situations,Alors...s[i]Remplacer par‘#’No.,Et puiss[i - 1]Le cas échéant,Et aussi avecs[i+1]Comparaison. Ce sentiment de retour en arrière,La vérité est une sorte de pensée monotone. */
    public String removeDuplicateLetters(String s) {
    
        char[] arr = s.toCharArray();
        //  Notez combien il y a par caractère .
        int[] fx = new int[26];
        for (char c : arr) fx[c - 'a']++;
        // Poids mort.
        Stack<Character> sk = new Stack<>();
        int[] set = new int[26];
        for (int i = 0; i < arr.length; i++) {
    
            //  Mets le grand devant , Et il y a des caractères en double , Pour éliminer , Gardez l'avant aussi monotone que possible , Même si ce n'est pas monotone , Ce caractère doit être seulement 1- Oui..
            while (!sk.isEmpty() && sk.peek() > arr[i] && fx[sk.peek() - 'a'] != 1 && set[arr[i] - 'a'] == 0) {
    
                System.out.println(fx[sk.peek() - 'a']);
                --fx[sk.peek() - 'a'];
                set[sk.pop() - 'a'] = 0;
            }
            //  Ajouter de nouveaux caractères , Si le nouveau caractère a déjà été ajouté , Pas besoin d'ajouter ça , Après tout, les mêmes petits caractères doivent être placés devant le plus petit .
            if (set[arr[i] - 'a'] == 0) {
    
                //  Il n'y a pas de , Et les caractères qui sont relativement monotones par rapport aux caractères de la pile monotone .
                sk.push(arr[i]);
                //  Définir qu'il existe déjà dans la pile monotone .
                set[arr[i] - 'a'] = 1;
            } else --fx[arr[i] - 'a'];//  Caractères à supprimer , Donc le nombre doit être réduit 1
        }
        //  Combiner des caractères relativement monotones en chaînes monotones .
        StringBuilder sb = new StringBuilder();
        while (!sk.isEmpty()) sb.insert(0, sk.pop());
        return sb.toString();
    }

    public static void main(String[] args) {
    
        new RemoveDuplicateLetters().removeDuplicateLetters("abafdsfasfasdfasdfasdfasfsdagewha");
    }
}

2、Tableau natif+lenSubstitutionstack

// Une tentative audacieuse, Remplacer la pile par un tableau .
// Bien sûr., Les tableaux natifs sont vraiment rapides .
class RemoveDuplicateLetters2 {
    
    /* target：Supprimer les lettres en double,L'ordre minimal du dictionnaire qui doit renvoyer les résultats est. Quands[i] >= s[i+1]Ets[i]Il y a beaucoup de situations,Alors...s[i]Remplacer par‘#’No.,Et puiss[i - 1]Le cas échéant,Et aussi avecs[i+1]Comparaison. Ce sentiment de retour en arrière,La vérité est une sorte de pensée monotone. */
    public String removeDuplicateLetters(String s) {
    
        char[] arr = s.toCharArray();
        //  Notez combien il y a par caractère .
        int[] fx = new int[26];
        for (char c : arr) fx[c - 'a']++;
        // Poids mort.
        char[] sk = new char[s.length()];
        int skLen = 0;
        int[] set = new int[26];
        for (int i = 0; i < arr.length; i++) {
    
            //  Mets le grand devant , Et il y a des caractères en double , Pour éliminer , Gardez l'avant aussi monotone que possible , Même si ce n'est pas monotone , Ce caractère doit être seulement 1- Oui..
            while (skLen != 0 && sk[skLen - 1] > arr[i] && fx[sk[skLen - 1] - 'a'] != 1 && set[arr[i] - 'a'] == 0) {
    
                System.out.println(fx[sk[skLen - 1] - 'a']);
                --fx[sk[skLen - 1] - 'a'];
                set[sk[--skLen] - 'a'] = 0;
            }
            //  Ajouter de nouveaux caractères , Si le nouveau caractère a déjà été ajouté , Pas besoin d'ajouter ça , Après tout, les mêmes petits caractères doivent être placés devant le plus petit .
            if (set[arr[i] - 'a'] == 0) {
    
                //  Il n'y a pas de , Et les caractères qui sont relativement monotones par rapport aux caractères de la pile monotone .
                sk[skLen++] = arr[i];
                //  Définir qu'il existe déjà dans la pile monotone .
                set[arr[i] - 'a'] = 1;
            } else --fx[arr[i] - 'a'];//  Caractères à supprimer , Donc le nombre doit être réduit 1
        }
        //  Combiner des caractères relativement monotones en chaînes monotones .
        StringBuilder sb = new StringBuilder();
        while (skLen != 0) sb.insert(0, sk[--skLen]);
        return sb.toString();
    }

}

Résumé

1） Les mots les plus importants , Associations avides de connaissances ; Impliquant l'ordre / Classes de taille avant et arrière , Point de connaissance de la pile monotone associative .
2）Tableauhash/Pile d'émulation de tableau,Par rapport àHashMap/StackCatégorie,Plus vite., Tout comme le tri de tas natif est plus rapide que la file d'attente prioritaire .

Références

[1] LeetCode Supprimer les lettres en double