给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc" 输出："abc" 示例 2：
输入：s = "cbacdcbc" 输出："acdb"
提示：
1 <= s.length <= 104 s 由小写英文字母组成
注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/remove-duplicate-letters
思路：
1. 定义一个map, 遍历数组，key 为字符，value 为字符在数组中最后出现的位置。遍历字符串，并将字符最后出现的位置更新到 map 中
2. 定义一个堆栈 Stack，保证该堆栈为单调栈，即从栈底到栈顶的字符串满足最小字典序
3. 遍历字符串中的每一个字符：
3.1) 当栈为空时，将当前字符压入Stack中
3.2) 当栈不为空时
3.2.1) 当前字符的字典序大于栈顶字符时，则将当前字符压入Stack
3.2.2) 当前字符的字典序小于栈顶字符时，
3.2.2.1) 若是栈顶字符最后出现的位置小于当前字符的 index 且栈中不存在当前字符（若是存在该字符，说明当前字符与栈顶字符已经满足最小字典序了），说明后面不再有栈顶字符了，此时将当前字符压入Stack中；
3.2.2.2) 若是栈顶字符最后出现的位置大于当前字符的 index，说明后面还有栈顶字符，为了保证字典序最小，将栈顶字符弹出；
并循环3.2.2.2 过程，直到Stack 为空或者 栈顶字符最后出现的位置小于当前字符的 index 终止循环
java代码：
class Solution {
public String removeDuplicateLetters(String s) {
// key 为字符，value 为字符在数组中最后出现的位置
Map
for (int index = 0; index < s.length(); index++) {
map.put(s.charAt(index), index);
}
Stack
for (int index = 0; index < s.length(); index++) {
if (stack.isEmpty()) {
stack.push(s.charAt(index));
} else {
// 当前字符的字典序大于栈顶字符时
if (s.charAt(index) > stack.peek()) {
if (!stack.contains(s.charAt(index))) {
stack.push(s.charAt(index));
}
} else {
// 当前字符的字典序小于栈顶字符时
while (!stack.isEmpty() &&s.charAt(index) < stack.peek() && !stack.contains(s.charAt(index))&& map.get(stack.peek()) > index) {
stack.pop();
}
if (stack.isEmpty()) {
stack.push(s.charAt(index));
} else if (!stack.contains(s.charAt(index))) {
stack.push(s.charAt(index));
}
}
}
}
Stack
while (!stack.isEmpty()) {
resultStack.push(stack.pop());
}
StringBuilder stringBuilder = new StringBuilder();
while (!resultStack.isEmpty()) {
stringBuilder.append(resultStack.pop());
}
return stringBuilder.toString();
}
}
发表评论