LeetCode 316. Remove Duplicate Letters（貪心）

• 2020 年 3 月 17 日
• 筆記

題目

題意：刪除重複的字元，得到字典序最小的結果字元串

題解：貪心，咱們從結果字元串的左邊開始，左邊第一個字元在原字元串中的右邊一定有n-1個不同的字元，這裡n就是結果字元串的長度。 所以我們每次遍曆數組，找到右邊有n-1個不同字元的字元，並選擇最小的那個。 由於最多26個字母，最多遍歷26次，所以不會超時 注意，要標記字元串是否被刪除過。

class Solution {  public:      int vis[30];      int m[30];      string ans;      int res;      int b=-1;      string removeDuplicateLetters(string s) {            if(s=="")              return "";          memset(vis,0,sizeof(vis));          int pos = 0;          while(1)          {              pos = fun(s,pos);              ans+=(res+'a');              vis[res]=1;              if(ans.length()==b)                  break;          }            return ans;        }        int fun(string s,int pos)      {          memset(m,0,sizeof(m));            int x=0;          res = 31;          int j=-2;          for(int i=s.length()-1;i>=pos;i--)          {              if(vis[s[i]-'a']==1)                  continue;              if(m[s[i]-'a']==0)              {                  x++;                  m[s[i]-'a']=1;                  res = s[i]-'a';                  j=i;              }              else              {                  if(res>=s[i]-'a')                  {                      res=s[i]-'a';                      j=i;                  }              }          }            if(b == -1)              b=x;            return j+1;      }  };