题目描述
给定一个整数，给出消除重复数字以后最大的整数
输入描述：
正整数，注意考虑长整数
输出描述
消除重复数字后的最大整数
示例1
输入
423234
输出
432
思路分析 ：要保存原来的顺序这个题目才有意思，如果不保存原来的顺序，那直接一个set就搞定了。
很明显这个数字的最大长度不会超过20。怎么暴力都可以了...
思路就是贪心的放每一位ie数字，
比如423234
我们放完第一个4 再放2的时候直接放入，再放3的时候发现前面的2比3小，而且2还有一个剩余，那么我们就用3替换2,一次类推....实现的时候我们可以用栈去搞
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll n, tmp; vector<int> cnt(10); vector<int> s; vector<int> vis(10); cin >> n; tmp = n; while(tmp > 0) { cnt[tmp%10]++; // cnt[i] 记录i出现过几次 s.push_back(tmp%10); //s用来存n的每一位 tmp /= 10; } reverse(s.begin(), s.end()); stack<int> st; //这个栈用来存我们构造的最优的序列 for (int i = 0; i < s.size(); ++i) { //cout << s[i] << endl; cnt[s[i]]--; //用完s[i]那么s[i]的个数-- if (st.empty()) { st.push(s[i]); vis[s[i]] = 1; //s[i]进栈 } else { while(!st.empty() && st.top() < s[i] && cnt[st.top()] && !vis[s[i]]) { //如果当前数比栈末尾那个数大，尝试去把栈末尾那个数弹出 vis[st.top()] = 0; //并用大的去替换，但是如果栈末尾的那个数没有多余的我们就替换不了 st.pop(); } if (!vis[s[i]]) st.push(s[i]), vis[s[i]] = 1; } } ll ans = 0, T = 1; while (!st.empty()) { ll x = st.top();st.pop(); ans += x*T; T *= 10; } cout << ans << endl; return 0; }