当前位置 博文首页 > 孙中明：LeetCode每日打卡-316. 去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"
输出："abc"
示例 2：
输入：s = "cbacdcbc"
输出："acdb"
提示：
1 <= s.length <= 104
s 由小写英文字母组成
思路
要删除已重复的字符，可以在第一次遍历时查询是否重复，而在生成处理后的字符时，需要能快速找到该字符第一次出现的位置，那么可以在第一次遍历时维护一个HashMap<Character,Integer>。
第一次遍历字符串时，若当前遍历的字符不在map中，将该字符和在字符串中的位置存入map中；已存在map中则不作操作。
第二次遍历字符串时，若当前字符在map中，将该字符保留，并且删除该字符的键值对；若不存在，不作操作。这样就可以得到保留第一次出现的字符。
代码
import java.util.*;
class Solution {
public String removeDuplicateLetters(String s) {
int len=s.length();
if(s==null||len<1){
return "";
}
StringBuffer res=new StringBuffer();
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(int i=0;i<=len-1;i++){
if(!map.containsKey(s.charAt(i))){
map.put(s.charAt(i),i);
}
}
for(int i =0;i<=len-1;i++){
if(map.containsKey(s.charAt(i))){
res.append(s.charAt(i));
map.remove(s.charAt(i),i);
}
}
return res.toString();
}
}
这样做的话就不能保证返回结果的字典序最小；所以我们需要用到栈
输入 "bcabc"
输出 "bca"
预期结果 "abc"
思路
用一个vis数组，如果这个字符入栈了，那么我们就把他标记为1，即有这个字符了，当他再出现，我们就不要了，直接跳过；
当一个s[i]>s[i+1]（准确一点应该是栈中前一个数大于后一个数时，类似于单调栈）时，i就可以被弹出去了，但是如果这个s[i]是独苗（后面再没有这个字符了），就不能弹出去了，那么我们用一个num数组存储s中剩余字符的情况，每当我们抛出一个字符或者我们跳过一个数的时候，其数都要减1；
import java.util.Stack;
/**
* 栈操作 o(n*log(n))
*/
public class Solution {
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
if (stack.contains(c)) {
continue;
}
//public int indexOf(int ch, int fromIndex): 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
while (!stack.isEmpty() && stack.peek() > c && s.indexOf(stack.peek(), i) != -1) {
stack.pop();
}
stack.push(c);
}
String rs = "";
for (int i = 0; i < stack.size(); i++) {
rs += stack.get(i);
}
return rs;
}
}
