本文主要是介绍51nod 1255 贪心（栈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
输入1行字符串S，所有字符均为小写，字符串的长度为L。(1 <= L <= 100000)。
输出包含S中所有出现过的字符，每个字符各1个，并且字典序最小的S的子序列。
babbdcc
abdc
题解：贪心，栈
分析：字母最多26个，数据范围可以不用太在意，因为是字典序，可以想象成从头开始的一个个试着加入一个数组中
思路：
第一步：栈为空，就直接加入一个元素
第二步：栈不为空，判断是否大于接下来要加入的元素，如果小于就直接加入（即字典序），否则判断一下后面是否还有栈顶元素
第三步：若还有栈顶元素，那么将栈顶 pop（）出来，若后面没有了自然就要留在栈里面了
第四步：把接下来的这个元素放入栈中
演示题目样例：
b 空栈直接加入
a 因为后面还有b，所以pop原有的b，放入a
ab 加入b
ab 已经有b了就不能再加了
abd 加入d
abdc 加入c
为什么这个贪心是正确的呢？
解：因为题目要的是字典序最小，如果要的是逆序数最小那就不正确了
这个解法一定保证了：贪心的最初的字母尽可能最小，依次类推即可得到答案
#include<stack>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int num[50];
bool vis[50];
char a[100010];
stack<int>st;int main()
{//freopen("in.txt","r",stdin);while(scanf("%s",a)!=EOF){while(!st.empty())st.pop();memset(num,0,sizeof(num));memset(vis,0,sizeof(vis));int len=strlen(a),temp;for(int i=0;i<len;i++){temp=a[i]-'a';num[temp]++;}for(int i=0;i<len;i++){temp=a[i]-'a';if(vis[temp]){///已在栈里面了num[temp]--;continue;}if(st.empty()){st.push(temp);vis[temp]=1;num[temp]--;}else{while(!st.empty()&&st.top()>temp){if(num[st.top()])vis[st.top()]=0,st.pop();elsebreak;}st.push(temp);vis[temp]=1;num[temp]--;}}int pos=0;char ans[50];while(!st.empty()){ans[pos++]=st.top()+'a';st.pop();}for(int i=pos-1;i>=0;i--)printf("%c",ans[i]);puts("");}return 0;
}
这篇关于51nod 1255 贪心（栈）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
