Remove duplicate letters [greedy + monotonic stack (maintain monotonic sequence with array +len)]

Preface

When the design reaches the most word problem , Most of them involve greedy algorithms , This situation , Understand the process of greed by yourself , And then embodied in the code .
When it comes to relative order / Front and back size , Generally, we need to use monotone stack for maintenance , Common scenes ： Back to back hedge .
For monotone stacks /hash And so on , Can use array , You can still use arrays , stay JVM level , Do than API The layer is much faster , And simple and lightweight .

One 、 Remove duplicate letters

Two 、 greedy + Monotonic stack

1、stack

//  Take out the duplicate string 
public class RemoveDuplicateLetters {
    
    /* target： Remove duplicate letters , The lexicographic order of the returned result is the smallest .  When s[i] >= s[i+1] And s[i] There are many cases , Then put s[i] Replace with ‘#’ Number , then s[i - 1] If any , And s[i+1] Compare .  This feeling of going back , Truth is a monotonous stack of ideas . */
    public String removeDuplicateLetters(String s) {
    
        char[] arr = s.toCharArray();
        //  Record how many characters there are .
        int[] fx = new int[26];
        for (char c : arr) fx[c - 'a']++;
        //  duplicate removal .
        Stack<Character> sk = new Stack<>();
        int[] set = new int[26];
        for (int i = 0; i < arr.length; i++) {
    
            //  Put the big one in front , And there are repeated characters after it , Just eliminate , Keep the front as monotonous as possible , Even if it's not monotonous , That character must be only 1 individual .
            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;
            }
            //  Add new characters , If the new character has been added before , Don't add this , After all, try to put the same small characters in front of the smallest .
            if (set[arr[i] - 'a'] == 0) {
    
                //  There is no , And it is relatively monotonous with the characters in the monotone stack .
                sk.push(arr[i]);
                //  Set that it already exists in the monotone stack .
                set[arr[i] - 'a'] = 1;
            } else --fx[arr[i] - 'a'];//  Characters to be removed , So the number needs to be reduced 1
        }
        //  Combine relatively monotonous characters into monotonic strings .
        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、 Native array +len replace stack

//  Try it out , Replace stack with array .
//  Sure enough , Native arrays are really fast .
class RemoveDuplicateLetters2 {
    
    /* target： Remove duplicate letters , The lexicographic order of the returned result is the smallest .  When s[i] >= s[i+1] And s[i] There are many cases , Then put s[i] Replace with ‘#’ Number , then s[i - 1] If any , And s[i+1] Compare .  This feeling of going back , Truth is a monotonous stack of ideas . */
    public String removeDuplicateLetters(String s) {
    
        char[] arr = s.toCharArray();
        //  Record how many characters there are .
        int[] fx = new int[26];
        for (char c : arr) fx[c - 'a']++;
        //  duplicate removal .
        char[] sk = new char[s.length()];
        int skLen = 0;
        int[] set = new int[26];
        for (int i = 0; i < arr.length; i++) {
    
            //  Put the big one in front , And there are repeated characters after it , Just eliminate , Keep the front as monotonous as possible , Even if it's not monotonous , That character must be only 1 individual .
            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;
            }
            //  Add new characters , If the new character has been added before , Don't add this , After all, try to put the same small characters in front of the smallest .
            if (set[arr[i] - 'a'] == 0) {
    
                //  There is no , And it is relatively monotonous with the characters in the monotone stack .
                sk[skLen++] = arr[i];
                //  Set that it already exists in the monotone stack .
                set[arr[i] - 'a'] = 1;
            } else --fx[arr[i] - 'a'];//  Characters to be removed , So the number needs to be reduced 1
        }
        //  Combine relatively monotonous characters into monotonic strings .
        StringBuilder sb = new StringBuilder();
        while (skLen != 0) sb.insert(0, sk[--skLen]);
        return sb.toString();
    }

}

summary

1） Involve the most words , Lenovo is greedy for knowledge ; Involving order / Front and back size classes , Lenovo monotone stack knowledge points .
2） Array hash/ Array simulation stack , Compared with HashMap/Stack class , Much faster , Just as native heap sorting is faster than priority queues .

reference

[1] LeetCode Remove duplicate letters