Smallest Subsequence of Distinct Characters
给一个字符串数组, 求一个最小的子序列, 其中包含不同的字符. 并且要求是字典序的顺序. 这个题开始的时候想复杂了, 我以为要用pq去排序字符串, 后来做的过不去test case, 然后看了眼答案, 发现可以用stack解决顺序的问题. 就是用一个数组记录一下是否已经在stack中, 然后stack里如果顶部的字符小于当前字符, 并且当前字符没有其他的, 就放到答案里, 如果不是就弹出.
class Solution {
public String smallestSubsequence(String text) {
StringBuilder sb = new StringBuilder();
Stack<Character> st = new Stack<>();
boolean[] visited = new boolean[256];
int[] count = new int[256];
for(char c : text.toCharArray()){
count[c -'a'] ++;
}
for(char c : text.toCharArray()) {
count[c - 'a']--;
if(visited[c - 'a']){
continue;
}
while(!st.isEmpty() && st.peek() > c && count[st.peek() - 'a'] > 0) {
visited[st.pop() - 'a'] = false;
}
visited[c - 'a'] = true;
st.push(c);
}
while(!st.isEmpty()){
sb.append(st.pop());
}
sb.reverse();
return new String(sb);
}
}