删除C ++中的重复字母
为了解决这个问题,我们将遵循以下步骤-
ans:=一个空字符串
定义一个堆栈st
在大小为26的onStack上定义一个数组
定义一张映射
n:=s的大小
用于初始化i:=0,当i<n时,将i增加1做-
将m[s[i]]增加1
用于初始化i:=0,当i<n时,将i增加1做-
onStack[st-'a'的顶部]:=false
从st删除项目
跳到下一个迭代,忽略以下部分
定义一个数组x=s,其大小为i
递减m[x]1
如果onStack[x-'a']不为零,则
当st不为空且x<st.top()时,执行-
将x插入st
onStack[x-'a']:=true
当(st为空)为false时,执行-
x:=st的顶部元素
从st删除项目
ans=ans+x
反转阵列转速
返回ans
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: string removeDuplicateLetters(string s) { string ans = ""; stack <char> st; vector <int> onStack(26); map <char, int> m; int n = s.size(); for(int i = 0; i < n; i++){ m[s[i]]++; } for(int i = 0; i < n; i++){ char x = s[i]; m[x]--; if(onStack[x - 'a'])continue; while(!st.empty() && x < st.top() && m[st.top()]){ onStack[st.top() - 'a'] = false; st.pop(); } st.push(x); onStack[x - 'a'] = true; } while(!st.empty()){ char x = st.top(); st.pop(); ans += x; } reverse(ans.begin(), ans.end()); return ans; } }; main(){ Solution ob; cout << (ob.removeDuplicateLetters("abccb")); }
输入项
“abccb”
输出结果
“abc”