Smallest Subsequence of Distinct Characters
给一个字符串数组, 求一个最小的子序列, 其中包含不同的字符. 并且要求是字典序的顺序. 这个题开始的时候想复杂了, 我以为要用pq去排序字符串, 后来做的过不去test case, 然后看了眼答案, 发现可以用stack解决顺序的问题. 就是用一个数组记录一下是否已经在stack中, 然后stack里如果顶部的字符小于当前字符, 并且当前字符没有其他的, 就放到答案里, 如果不是就弹出.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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); } } |