316. Remove Duplicate Letters

chunquedong 發(fā)布于2019-08-19 10:45 / 2384人閱讀

摘要：以及枚舉的做法，因?yàn)檫@題只有個(gè)字母，枚舉的復(fù)雜度是，參考博客還有先把排序，然后從小到大取字母的寫(xiě)法，參考

316. Remove Duplicate Letters

題目鏈接：https://leetcode.com/problems...

用一個(gè)stack來(lái)做，stack里面的字母按增序來(lái)排，出現(xiàn)top>cur的時(shí)候要把top給pop出來(lái)，注意一點(diǎn)是如果后面沒(méi)有top的話，就不能pop出來(lái)，所以先要用個(gè)hashmap來(lái)保存每個(gè)字母出現(xiàn)的次數(shù)，次數(shù)到0說(shuō)明后面沒(méi)有這個(gè)字母了，還需要一個(gè)visited數(shù)組來(lái)保存已經(jīng)在stack里面的字母

pop: while top > cur && map[top] > 0

push: when !visited[cur]

loop invariant是(0, i)是到i為止最小的字母order結(jié)果。

public class Solution {
    public String removeDuplicateLetters(String s) {
        // count the number of each character
        int[] map = new int[26];
        for(char c : s.toCharArray()) {
            map[c - "a"]++;
        }
        // stack to store the smallest lexi order
        char[] stack = new char[s.length()];
        // visited to record already added letter
        boolean[] visited = new boolean[26];
        int i = 0;
        for(char c : s.toCharArray()) {
            map[c - "a"]--;
            if(visited[c - "a"]) continue;
            // pop top character if it is > c && there are remains in the right
            while(i > 0 && stack[i-1] > c && map[stack[i-1] - "a"] > 0) {
                visited[stack[i-1] - "a"] = false;
                i--;
            }
            stack[i++] = c;
            visited[c-"a"] = true;
        }
        
        return new String(stack, 0, i);
    }
}

以及枚舉的做法，因?yàn)檫@題只有26個(gè)字母，枚舉的復(fù)雜度是O(26*N)，參考博客：
http://bookshadow.com/weblog/...

還有先把string排序，然后從小到大取字母的寫(xiě)法，參考discussion：
https://discuss.leetcode.com/...