Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example：

Input: "bcabc"
Output: "abc"

Input: "cbacdcbc"
Output: "acdb"

解釋下題目：

題目其實(shí)很簡(jiǎn)單，就是把重復(fù)的刪除，然后因?yàn)閯h除可能有很多種可以刪除的選擇，留下字典順序最小的。舉個(gè)例子，babc明顯要?jiǎng)h除一個(gè)b，所以如果選擇刪除第一個(gè)b，剩下的是abc，如果選擇第二個(gè)b，那么留下的是bac，顯然是abc<bac。

1. 錯(cuò)誤的貪心算法

實(shí)際耗時(shí)：錯(cuò)誤的

public String removeDuplicateLetters(String s) {
        int position = 0;
        HashMap<Integer, Character> result = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) {
            if (s.indexOf(c) != -1) {
                //存在這個(gè)字符，那么先在position之后找有沒(méi)有它的位子
                for (int i = position; i < s.length(); i++) {
                    if (s.charAt(i) == c) {
                        position = i;
                        break;
                    }
                }
                //如果后面沒(méi)找到
                if (s.charAt(position) != c) {
                    position = s.indexOf(c);
                }

                result.put(position, c);
            } else {
                //不存在這個(gè)字符，什么都不用做
            }
        }

        for (Map.Entry<Integer, Character> entry : result.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }

        return "";
    }

??思路，這里先假設(shè)一定有abc字符（因?yàn)閾Q成其他的也成立），然后我首先要找a，肯定希望a越前面越好，這樣后面所剩下的空間越大。OK現(xiàn)在有了第一個(gè)字符位置確定了，第二個(gè)b有幾種可能：

1. b只有在a之后才有，這樣的話肯定留下離a距離最近的，理由同選擇a的時(shí)候一樣。
2. b只有在a之前才有，那么就要使b在數(shù)組越前面越好。理由同選擇a的時(shí)候一樣。
3. b在a前后都有。我錯(cuò)就錯(cuò)在這里，其實(shí)這種情況是需要討論的，我錯(cuò)誤的解法就認(rèn)為肯定要選擇在a之后且離a最近的那個(gè)b，這就導(dǎo)致了可能會(huì)出現(xiàn)c的位置放不好了。解決方法是用一個(gè)數(shù)組記錄下有沒(méi)有出現(xiàn)過(guò)。
   舉個(gè)會(huì)發(fā)生錯(cuò)誤的例子：cbacdcbc，肉眼看一下答案應(yīng)該是acdb，但是算法的結(jié)果是adbc，判斷過(guò)程簡(jiǎn)單寫(xiě)一下：首先a肯定沒(méi)問(wèn)題，然后b按照思路會(huì)選擇倒數(shù)第二個(gè)b，這也沒(méi)問(wèn)題，問(wèn)題在于c的選擇。按照我的算法會(huì)選擇在b之后且離b最近的那個(gè)c，這就導(dǎo)致了d會(huì)出現(xiàn)在bc之前，就是沒(méi)考慮好，具體解決見(jiàn)方法2。

時(shí)間復(fù)雜度O(n) n為string的長(zhǎng)度

空間復(fù)雜度O(1)

2.利用堆棧實(shí)現(xiàn)

實(shí)際耗時(shí)：3ms

 public String removeDuplicateLetters2(String s) {
        Stack<Character> stack = new Stack<>();

        //1.計(jì)算每個(gè)字母出現(xiàn)的次數(shù)
        int[] count = new int[26];
        char[] arr = s.toCharArray();
        for (char c : arr) {
            count[c - 'a']++;
        }

        boolean[] visited = new boolean[26];

        //2. 對(duì)每個(gè)字母進(jìn)行處理
        for (char c : arr) {
            count[c - 'a']--;

            //已經(jīng)處理過(guò)這個(gè)字符了，無(wú)需處理
            if (visited[c - 'a']) {
                continue;
            }

            //3. 如果頂端的那個(gè)字母比現(xiàn)在的這個(gè)小，如堆棧的頂端是c，而目前的是a，且c之后還會(huì)出現(xiàn)的話，那這個(gè)c我就不要了
            while (!stack.isEmpty() && stack.peek() > c && count[stack.peek() - 'a'] > 0) {
                visited[stack.peek() - 'a'] = false;
                stack.pop();
            }
            stack.push(c);
            visited[c - 'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (char c : stack) {
            sb.append(c);
        }
        return sb.toString();
    }

??思路很簡(jiǎn)單，就跟撿東西一樣，如果我之后還能撿到，那我現(xiàn)在就可以先不要，仔細(xì)理解一下3.的注釋就可以了。

時(shí)間復(fù)雜度O(n)

空間復(fù)雜度O(n)