去除重複字母[貪心+單調棧(用數組+len來維持單調序列)]

前言

當設計到最字問題時，多半涉及了貪心算法，這種情况，要自己去理解貪心過程，然後再體現在代碼中。
當涉及到相對有序/前後大小之類的，一般就需要用單調棧來做維護，常見場景：往回比往回對沖。
對於單調棧/hash之類，能用數組的情况，還是可以用數組，在JVM層面，確實比API層面快很多，而且簡潔輕量。

一、去除重複字母

二、貪心+單調棧

1、stack

// 取出重複字符串
public class RemoveDuplicateLetters {
    
    /* target：去除重複字母，需要返回結果的字典序最小。 當s[i] >= s[i+1]且s[i]有又多的情况下，則把s[i]替換成‘#’號，然後s[i - 1]如果有的話，也要和s[i+1]比較。 這種往回比的感覺，屬實是單調棧一類思想了。 */
    public String removeDuplicateLetters(String s) {
    
        char[] arr = s.toCharArray();
        // 記錄每個字符有多少個。
        int[] fx = new int[26];
        for (char c : arr) fx[c - 'a']++;
        // 去重。
        Stack<Character> sk = new Stack<>();
        int[] set = new int[26];
        for (int i = 0; i < arr.length; i++) {
    
            // 把前面大的，且後面還有重複的字符，就消除掉，盡可能讓前面保持單調，即使不單調，那個字符肯定是只有1個。
            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;
            }
            // 把新字符加入，如果新字符前面已經加入過了，就不用加這個了，畢竟相同的小字符盡量放到前面最小。
            if (set[arr[i] - 'a'] == 0) {
    
                // 加入單調棧中沒有，且和單調棧中字符成相對單調的字符。
                sk.push(arr[i]);
                // 設置其已在單調棧中存在。
                set[arr[i] - 'a'] = 1;
            } else --fx[arr[i] - 'a'];// 需要去除的字符，所以個數需要减1
        }
        // 把相對單調的字符組合成單調字符串。
        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、原生數組+len替代stack

// 大膽嘗試，用數組替換棧。
// 果然，原生數組是真的快。
class RemoveDuplicateLetters2 {
    
    /* target：去除重複字母，需要返回結果的字典序最小。 當s[i] >= s[i+1]且s[i]有又多的情况下，則把s[i]替換成‘#’號，然後s[i - 1]如果有的話，也要和s[i+1]比較。 這種往回比的感覺，屬實是單調棧一類思想了。 */
    public String removeDuplicateLetters(String s) {
    
        char[] arr = s.toCharArray();
        // 記錄每個字符有多少個。
        int[] fx = new int[26];
        for (char c : arr) fx[c - 'a']++;
        // 去重。
        char[] sk = new char[s.length()];
        int skLen = 0;
        int[] set = new int[26];
        for (int i = 0; i < arr.length; i++) {
    
            // 把前面大的，且後面還有重複的字符，就消除掉，盡可能讓前面保持單調，即使不單調，那個字符肯定是只有1個。
            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;
            }
            // 把新字符加入，如果新字符前面已經加入過了，就不用加這個了，畢竟相同的小字符盡量放到前面最小。
            if (set[arr[i] - 'a'] == 0) {
    
                // 加入單調棧中沒有，且和單調棧中字符成相對單調的字符。
                sk[skLen++] = arr[i];
                // 設置其已在單調棧中存在。
                set[arr[i] - 'a'] = 1;
            } else --fx[arr[i] - 'a'];// 需要去除的字符，所以個數需要减1
        }
        // 把相對單調的字符組合成單調字符串。
        StringBuilder sb = new StringBuilder();
        while (skLen != 0) sb.insert(0, sk[--skLen]);
        return sb.toString();
    }

}

總結

1）涉及最字，聯想貪心知識點；涉及有序/前後大小類，聯想單調棧知識點。
2）數組hash/數組模擬棧，比起HashMap/Stack類，要快很多，就像原生堆排序比優先隊列快一樣。

參考文獻

[1] LeetCode 去除重複字母