练习题 去除重复字母

题目

给你一个字符串?s?，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证?返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 104
• s?由小写英文字母组成

注意：该题与 1081?. - 力扣（LeetCode）?相同

提交代码

//去除重复字母

//保证每个字母只出现一次
//删除后尽可能字典序最小
//字符串字典序最小 -> 整数最小 
//需要先判断各个字符的出现次数 
//改良后的单调栈，存的字符从小到大但只出现一次的字符不出栈
//需要判断和上个数直接的关系 

#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
using namespace std; 

string s;//字符串
int n;//字符串长度 
string result;//结果字符串
//有默认值 
int c[26];//存储各个字符的出现次数 
stack<int> stk;//改良后的单调栈
bool inStack[26];//该字符是否已经在栈中 

//改后单调栈
void monotonicStack(int p){
	
	while(!stk.empty()){
		if(inStack[s[p] - 'a']){
			//该字符已经在栈中了 
			c[s[p] - 'a']--;
			return;
		}
			
		if(stk.top() >= s[p]){
			if(c[stk.top() - 'a'] != 0){
				//后面还有栈顶这个元素
				inStack[stk.top() - 'a'] = false; 
				stk.pop(); 
			}else{
				//后面没有栈顶元素了 
				break;
			}
		}else{
			break;
		}
	}
	
	c[s[p] - 'a']--;
	inStack[s[p] - 'a'] = true;
	stk.push(s[p]);
} 

int main(){
	//输入整数数组  
	/*int t; 
	
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		nums.push_back(t);
	}*/
	
	//输入字符串
	cin >> s; 
	
	//-------------------------------
	
	n = s.length();//字符串长度
	
	//先判断各个字符出现的次数
	for(int i = 0;i < n;i++){
		c[s[i] - 'a']++;
	} 
	
	//改后单调栈
	//从前到后遍历字符串
	for(int i = 0;i < n;i++){
		monotonicStack(i);
	} 
	
	//获取单调栈中所有的内容
	while(!stk.empty()){
		result += stk.top();
		stk.pop();
	}
	
	//反转结果字符串
	reverse(result.begin(),result.end()); 
	
	//输出结果
	cout << result;
	
	return 0;
} 

总结

解题思路：字母组成的字典序最小，本质就相似于最小整数，所以其实就是要尽可能把这个元素放在上一个比它小的元素的后面，可以使用单调栈。但注意，这道题目中，所以元素都必须至少出现一遍，所以需要先提前遍历一遍记录各个元素总数，以便之后判断后面相同的元素还有几个。本题需要灵活使用单调栈，要出栈的元素应该大于当前元素且之后还会再出现才行。

注意：

? ? ? ? 全局变量有默认的初始值，如0、false、nullptr等，可以不用声明时赋值。