專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

據多家媒體報道，最近雷軍開出千萬年薪招攬了一位95后AI天才少女——DeepSeek開源大模型DeepSeek-V2的關鍵開發者之一羅福莉，她或供職于小米AI實驗室，領導小米大模型團隊。

羅福莉被關注的“傳奇人生”自2019年開始，身為北大碩士的她，因在NLP國際頂會ACL 上發表 8 篇論文（其中2篇一作）而迅速走紅，受到頗多關注。

畢業后，她又加入阿里達摩院機器智能實驗室。羅福莉主導開發的多語言預訓練模型 VECO(同時支持多語言理解和生成的跨語言模型)，被納入阿里達摩院深度語言模型體系 AliceMind。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第316題：去除重復字母。

問題描述

來源：LeetCode第316題

難度：中等

給你一個字符串 s ，請你去除字符串中重復的字母，使得每個字母只出現一次。需保證返回結果的字典序最小（要求不能打亂其他字符的相對位置）。

示例1：

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

示例2：

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

• 1 <= s.length <= 104

• s 由小寫英文字母組成

問題分析

這題是讓 刪除字符串 s 中的重復字符，使每個字符只出現一次，需要保證返回結果的字典序最小 ，并且還不能打亂字符的相對位置。

解決思路就是使用一個棧，然后遍歷字符串中的每個字符，如果當前字符在棧中出現了就不用管了，因為每個字符只能出現一次。

如果當前字符在棧中沒有出現，我們就需要把它添加到棧中，添加的時候因為要保證字典序最小，所以要和棧頂元素比較，如果當前字符比棧頂元素小并且棧頂元素在后面還會出現，就把棧頂元素給刪除，接著繼續重復上面的步驟。

舉個例子，比如棧中元素是[a,b,e]（右邊是棧頂），當我們添加字符 c 的時候，因為棧頂字符 e 比當前字符 c 大：

1，假設字符串后面還有 e ，這個時候我們就可以把 e 給移除掉，在后面的時候可以在加 e 。

2，假設字符串后面沒有 e 了，就不能把字符 e 給移除，因為移除之后，后面沒有了就沒法在添加了。

這里的關鍵點是怎么判斷后面還有沒有待移除的字符呢？很簡單，我們只需要在開始的時候計算每個字符的個數即可，用掉一個就減去一個。最后棧中的字符就是需要返回的結果，我們還需要把它轉化為字符串。

JAVA：

public String removeDuplicateLetters(String s) {     Stack
         
  stk =  new Stack<>(); // 棧      int[] count =  new  int[ 128]; // 統計每個字符的數量      for ( int i =  0; i < s.length(); i++)         count[s.charAt(i)]++;      // 記錄對應的字符有沒有添加到棧中      boolean[] add =  new  boolean[ 128];      for ( char ch : s.toCharArray()) {         count[ch]--; // 遍歷到當前字符，數量要減1          if (add[ch]) // 如果當前字符已經添加到棧中就跳過              continue;          // 如果當前字符沒有添加到棧中，棧頂字符比當前字符大          // 并且棧頂字符在后面還有，就讓棧頂字符出棧。          while (!stk.isEmpty() && stk.peek() > ch                 && count[stk.peek()] >  0) {             add[stk.pop()] =  false; // 標記為false         }         stk.push(ch); // 把當前字符添加到棧中         add[ch] =  true;     }      // 這里是把棧中的字符轉化為字符串。     StringBuilder sb =  new StringBuilder();      while (!stk.isEmpty())         sb.append(stk.pop());      return sb.reverse().toString(); }

C++：

public:     string removeDuplicateLetters(string s) {         stack

  stk;// 棧         vector

  count(128);// 統計每個字符的數量         for (char ch: s)             count[ch]++;         // 記錄對應的字符有沒有添加到棧中         vector

  add(128, false);         for (char ch: s) {             count[ch]--;// 遍歷到當前字符，數量要減1             if (add[ch])// 如果當前字符已經添加到棧中就跳過                 continue;             // 如果當前字符沒有添加到棧中，棧頂字符比當前字符大             // 并且棧頂字符在后面還有，就讓棧頂字符出棧。             while (!stk.empty() && stk.top() > ch && count[stk.top()] > 0) {                 add[stk.top()] = false;                 stk.pop();             }             stk.push(ch);// 把當前字符添加到棧中             add[ch] = true;         }         // 這里是把棧中的字符轉化為字符串。         string str;         while (!stk.empty()) {             str.push_back(stk.top());             stk.pop();         }         reverse(str.begin(), str.end());         return str;     }

Python：

def removeDuplicateLetters(self, s: str) -> str:     stk = []  # 棧     count = Counter(s)  # 統計每個字符的數量     # 記錄對應的字符有沒有添加到棧中     add = [0] * 128     for ch in s:         count[ch] -= 1  # 遍歷到當前字符，數量要減1         if add[ord(ch)]:  # 如果當前字符已經添加到棧中就跳過             continue             '''              如果當前字符沒有添加到棧中，棧頂字符比當前字符大             并且棧頂字符在后面還有，就讓棧頂字符出棧。             '''         while stk and stk[-1] > ch and count[stk[-1]] > 0:             add[ord(stk[-1])] = 0  # 標記為false             stk.pop()         stk.append(ch)  # 把當前字符添加到棧中         add[ord(ch)] = 1         # 這里是把棧中的字符轉化為字符串。     return ''.join(stk)

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。