​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：計算右側小于目前元素的個數