leetcode 316
给你一个字符串 s
,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)
分析:
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱s
中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。
String removeDuplicateLetters(String s) {
Stack<Character> stk = new Stack<>();
// 维护一个计数器记录字符串中字符的数量,用于判断后面还有没有该字符
// 因为输入为 ASCII 字符,大小 256 够用了
int[] count = new int[256];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i)]++;
}
boolean[] inStack = new boolean[256];
for (char c : s.toCharArray()) {
// 每遍历过一个字符,都将对应的计数减一
count[c]--;
// 去重
if (inStack[c]) continue;
// 将栈中比当前字符大且后面还有的字符pop掉
while (!stk.isEmpty() && stk.peek() > c) {
// 若之后不存在栈顶元素了,则停止 pop
if (count[stk.peek()] == 0) {
break;
}
// 若之后还有,则可以 pop
inStack[stk.pop()] = false;
}
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
return sb.reverse().toString();
}
总结
要求一、通过inStack
这个布尔数组做到栈stk
中不存在重复元素。
要求二、顺序遍历字符串s
,通过「栈」 记录结果字符串,保证字符出现的顺序和s
中出现的顺序一致。
要求三、用类似单调栈的思路,配合计数器count
不断 pop 掉不符合最小字典序的字符,保证了最终得到的结果字典序最小