題干：

CSL 以前不會(huì)字符串算法，經(jīng)過一年的訓(xùn)練，他還是不會(huì)……于是他打算向你求助。

給定一個(gè)字符串，只含有可打印字符，通過刪除若干字符得到新字符串，新字符串必須滿足兩個(gè)條件：

• 原字符串中出現(xiàn)的字符，新字符串也必須包含。
• 新字符串中所有的字符均不相同。
• 新字符串的字典序是滿足上面兩個(gè)條件的最小的字符串。

輸入描述:

僅一行，有一個(gè)只含有可打印字符的字符串 s。

|s|≤105|s|≤105

輸出描述:

在一行輸出字典序最小的新字符串。

示例1

輸入

復(fù)制

bab

輸出

復(fù)制

ab

示例2

輸入

復(fù)制

baca

輸出

復(fù)制

bac

備注:

ASCII字符集包含 94 個(gè)可打印字符(0x21 - 0x7E)，不包含空格。

解題報(bào)告：

? ? 這題是類似單調(diào)棧的思想，只不過彈出的時(shí)候要判斷一下是否后面還有改數(shù)字。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 1e5 + 5; string s; bool vis[MAX]; int bk[555],tot; stack<char > sk; int main() {cin>>s;int len = s.size();s = ' ' + s;for(int i = 1; i<=len; i++) {bk[s[i]]++;}string ans;int cur = 1,pos = 1;for(int i = 1; i<=len; i++) {char tar = s[i];bk[tar]--;if(vis[tar]) continue;while( sk.size() && bk[sk.top()] && tar < sk.top()) {vis[sk.top()] = 0;sk.pop();ans.pop_back();}ans += tar;sk.push(tar);vis[tar] = 1;}cout << ans << endl;return 0 ; } //bcdddbca

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 551D】CSL 的字符串（单调栈，思维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。