题目描述
给定一个十进制的正整数number，选择从里面去掉一部分数字，希望保留下来的数字组成的正整数最大。
输入描述:
输入为两行内容，第一行是正整数number，1 ≤ length(number) ≤ 50000。第二行是希望去掉的数字数量cnt 1 ≤ cnt < length(number)。
输出描述:
输出保留下来的结果。
示例1
输入
325 1
输出
35
题解
方法1. 因为想要最后剩下的数尽量大，所以贪心地从前往后找到某位数比后一位小就删掉这个数，但是这样需要 O(n*m) (n 是总位数，m 是删除的个数)。我们可以利用一个栈来达到 O(n)的时间复杂度：遍历每一位，当还能删除时且栈内的数比当前数小就出栈，直到栈内的数比当前数大，或者栈空，就将当前的数入栈。如果全部数都入过栈时还需要删除，那就从栈顶删。
sta = []#num = '0123456789's = input()n = m = int(input())for i in s: #while len(sta) != 0 and num.index(sta[-1]) < num.index(i) and m > 0: while len(sta) != 0 and sta[-1] < i and m > 0: m -= 1 sta.pop() sta.append(i) print (''.join(sta[:(len(s) - n)])) 方法2.
贪心的从头开始往后面查找前一个数比后一个数小的相邻两数，删除前面的数，当所有这种情况都删除，数字数量cnt还不为0，从后面删除剩余cnt个数的数。
（如果选择删除全部0，再删除全部1，再删除全部2的方法，这种贪心策略是错误的。例如：3450 1，正确结果应该为450）
#includeusing namespace std;const int maxn = 50005;char s[maxn];int stk[maxn]; int main(){ int cnt,top = -1; scanf("%s %d",s,&cnt); int len = strlen(s); for (int i = 0;i < len - 1;i++){ if (s[i] >= s[i + 1] || !cnt){ stk[++top] = s[i] - '0'; }else if (cnt && s[i] < s[i + 1]){ cnt--; while (cnt && top >= 0 && stk[top] < s[i + 1] - '0'){ top--; cnt--; } } } stk[++top] = s[len - 1] - '0'; while (cnt){ cnt--; top--; } for (int i = 0;i <= top;i++){ printf("%d",stk[i]); } printf("\n"); return 0;}//https://www.cnblogs.com/zzy19961112/p/8525873.html