http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1255
思路:
分三种情况:
1:栈空,直接将字母压入。
2:栈非空,当前字母大于栈顶元素,栈中未出现该字母,压入栈。
3:栈非空,当前字母小于栈顶元素,栈中未出现该字母,执行循环:栈顶元素大于当前字母,且后面还存在栈顶元素,弹出栈顶元素。最后压入当前字母。
#include<iostream>
#include<stack>
#include<cstring>
#include<stdio.h>
#include<algorithm>
#define maxn 100005
using namespace std;
int coun[27];
bool juge[27];
char s[maxn];
int main()
{
scanf("%s",s);
int len=strlen(s);
for(int x=0;x<27;x++)
coun[x]=0,juge[x]=0;
for(int x=0;x<len;x++)
coun[s[x]-'a']++;
stack<char>s1,s2;
for(int x=0;x<len;x++)
{
coun[s[x]-'a']--;
if(s1.empty())
s1.push(s[x]),juge[s[x]-'a']=1;
else if(s[x]>s1.top()&&juge[s[x]-'a']==0&&!s1.empty())
s1.push(s[x]),juge[s[x]-'a']=1;
else if(!s1.empty()&&s[x]<s1.top()&&juge[s[x]-'a']==0)
{
while(!s1.empty()&&s[x]<s1.top()&&coun[s1.top()-'a']>0)
juge[s1.top()-'a']=0,s1.pop();
s1.push(s[x]);juge[s1.top()-'a']=1;
}
}
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
while(!s2.empty())
{
printf("%c",s2.top());
s2.pop();
}
printf("\n");
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)