題意：給定一個字符串辉懒，返回去除重復(fù)后嚎莉，安字典順序最大的字符串
思路：具體見代碼注釋
思想：雙向隊列
復(fù)雜度：時間O（n)，空間O(n)
class Solution {
public String removeDuplicateLetters(String s) {
//store the last index for each letter
int[] arr = new int[26];
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
arr[c-'a'] = i;
}
//keep track if letter has been added
HashSet<Character> set = new HashSet<>();
Deque<Character> stack = new ArrayDeque<>();
for(int i = 0; i< s.length(); i++) {
char c = s.charAt(i);
//always add letter if not yet added
if(!set.contains(c)) {
//keep removing if previous letter is bigger and the letter is available later
while(!stack.isEmpty() && (stack.peek() > c) && (arr[stack.peek()-'a'] > i)) {
char tmp = stack.pop();
set.remove(tmp);
}
set.add(c);
stack.push(c);
}
}
//append and reverse before return
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
