LeetCode刷题实战316：去除重复字母-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 去除重复字母，我们先来看题面：

https://leetcode-cn.com/problems/remove-duplicate-letters/

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

解题

* 算法思想

* 当字典序最小时，即12341 12351 主要看4，5的位置

* 用栈存储，当栈空时直接入栈

* 栈不为空时，

* 若栈中包含当前要入栈的元素直接跳到下一次循环。（结果字符串每个字符只含有一次）

* 若当前要入栈的字母比栈顶字母大时，考虑是否栈顶元素出栈

* 若栈顶元素在剩余字符串中仍然存在，那么就可以出栈，出栈后继续判断新的栈顶元素是否出栈。

public class RemoveDuplicateLetters {

    public static String removeDuplicateLetters(String s){
        Stack<Character> stack = new Stack<Character>();
            for (int i = 0; i < s.length(); i++) {
                char c=s.charAt(i);
                if(stack.contains(c))
                    continue;
                while(!stack.isEmpty() && stack.peek()>c && s.indexOf(stack.peek(),i)!=-1)
                    stack.pop();
                stack.push(c);
            }
            char chars[]=new char[stack.size()];
            for (int i = 0; i < stack.size(); i++) {
                chars[i]=stack.get(i);
            }
            return new String(chars);
    }

    public static void main(String[] args) {
        String string = "bbcaac";
        System.out.println(removeDuplicateLetters(string));
    }
}