20、去除重复字母

题目描述:
给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例 1:

输入: “bcabc”
输出: “abc”
示例 2:

输入: “cbacdcbc”
输出: “acdb”
用栈来解决,需要注意的是,每次遍历一个字母时,我们首先看是否已经放入,如果已经有了忽略,如果没有并且栈比顶小,并且栈顶字母后面还会出现,那么我们弹出栈顶,并且设置栈顶元素没有放入,继续遍历,接着我们判断当前字母是否在栈里面存在,如果存在那么就不需要放入了,但是要将次数减一,然后继续循环,如果没有那么设置已经存在,然后入栈。
代码:

class Solution {
    public String removeDuplicateLetters(String s) {
        int []tem = new int[26];
		for (int i = 0; i < s.length(); i++) {
			char tems = s.charAt(i);
			tem[tems - 'a'] ++;
		}
		boolean visited[] = new boolean[26];
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			char get = s.charAt(i);
			while (!stack.isEmpty() && stack.peek() > get 
					&& !visited[get - 'a']
					&& tem[stack.peek() - 'a'] > 0
					) {
				visited[stack.peek() - 'a'] = false;
				stack.pop();
			}
			if(visited[get - 'a']){
				tem[get - 'a'] --;
				continue;
			}
			visited[get - 'a'] = true;
			stack.push(get);
            tem[get - 'a'] --;
		}
		StringBuilder sBuilder = new StringBuilder();
		while (!stack.isEmpty()) {
			sBuilder.append(stack.pop());
		}
		
		return sBuilder.reverse().toString();
    }
}
上一篇:第八天 0716


下一篇:暴力贪心+预处理自动机——cf990E