​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));
    }
}
           

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-300题汇总，希望对你有点帮助！

LeetCode刷题实战301：删除无效的括号

LeetCode刷题实战302：包含全部黑色像素的最小矩阵

LeetCode刷题实战303：区域和检索 - 数组不可变

LeetCode刷题实战304：二维区域和检索 - 矩阵不可变

LeetCode刷题实战305：岛屿数量II

LeetCode刷题实战306：累加数

LeetCode刷题实战307：区域和检索 - 数组可修改

LeetCode刷题实战308：二维区域和检索 - 可变

LeetCode刷题实战309：最佳买卖股票时机含冷冻期

LeetCode刷题实战310：最小高度树

LeetCode刷题实战311：稀疏矩阵的乘法

LeetCode刷题实战312：戳气球

LeetCode刷题实战313：超级丑数

LeetCode刷题实战314：二叉树的竖直遍历

LeetCode刷题实战315：计算右侧小于当前元素的个数