N 位数删除 K 个数字，使剩下的数字最小

题目描述：
给定一个十进制的正整数 number，该正整数有 N 位，选择从里面去掉 K 个数字，希望留下来的数字组成的正整数最小。

输入描述：
输入为两个数字，第一个数字是一个正整数 number， 1<=length(number)<=50000。第二个数字是希望去掉的数字数量 cnt， 并且 1<=cnt<=length(number)。

输出描述：
输出保留下来的结果。

示例：

输入
124682385 2

输出
1242385

思路：
删除 K 个，可以使用贪心算法，每次删除 1 个。
那么每次删除哪一个呢？
如果 N>=2 的话，我们可以将该整数写成 XabY 的形式，其中 X 和 Y 分别是前缀和后缀，并且其长度可以为 0。因为 a 和 b 相邻并且 a 在 b 左边，所以删除一个的话，剩下的数就变成了 XaY 或 XbY 了。分下面两种情况讨论：
（1）若 a!=b 的话，为了使剩下的数最小，我们倾向于删除 a 和 b 中较大的那个数
（2）若 a==b 的话，删除 a 和删除 b 是等价的，所以我们就跳过 a，去比较 b 和它的后继，这就转变成了问题(1)了。

综上所述：
如果要使的剩下的数字最小，可以每次从左向右扫描，找出连续的非严格递增串，删除该串的最后一个数字。
如果要使剩下的数字最大，可以每次从左向右扫描，找出连续的非严格递减串，删除该串的最后一个数字。

下面给出求剩下数字最小的 C++ 代码：

string deleteKNumbers(string &str, int k)
{
	string::iterator start;
	bool flag;
	for(int i = k; i > 0; --i)
	{
		flag = 0;
		for(start = str.begin(); start < str.end() - 1; ++start)
		{
			 // 每次删除第一个比下一个数字大的数
			if(*start > *(start + 1))
			{
				str.erase(start);
				flag = 1;
				break;
			}
		}
		//如果所有数字递增，则删除最后几个数字直接返回
		if(!flag) 
		{
			str.erase(str.end() - i, str.end());
			break;
		}
	}
	return str;
}