把上一题做了优化,每新增一个元素就判断是否出现过,如果出现过,不加入队列,同时把队列中相同的元素出队;
每一次判断队列是否为空,不为空返回队首元素
class Solution{
public:
// count存每个元素出现的次数
unordered_map<char, int> count;
// 单调队列类似双指针,存一个有效区间,不需要的元素直接出队省空间
queue<char> q;
//Insert one char from stringstream
void insert(char ch){
if (++ count[ch] > 1) { // ch已存在
while (q.size() && count[q.front()] > 1)
q.pop(); //把已在队列,出现两次的元素出队
} else q.push(ch); // 未出现过的加入队列
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
if (q.empty()) return '#';
return q.front();
}
};