去除重复字母[贪心+单调栈(用数组+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 去除重复字母