316. 去除重复字母

题面:

316. 去除重复字母

 

 题解:单调栈

代码:

class Solution {
public:
    string removeDuplicateLetters(string s) {
             int n = s.size();
             vector<int> num(26,0),vis(26,0);
             string stk;
             for(int i = 0; i < n; i ++)
             {
                     num[s[i] - 'a'] ++;
             }
             for(int i = 0;i < n; i++  )
             {
                  if(!vis[s[i] - 'a'])
                  {
                      while(stk.size()&&stk.back() > s[i]&&num[stk.back() - 'a'] > 0)
                      {
                                vis[stk.back() - 'a'] = 0;
                                stk.pop_back();
                      }
                      vis[s[i] - 'a'] = 1;
                      stk.push_back(s[i]);
                  }
                  num[s[i] - 'a' ] --;
             }
             return stk;
    }
};

 

上一篇:Educational Codeforces Round 121 (Rated for Div. 2) ABC(区间求并)


下一篇:[COI2007] Patrik 音乐会的等待