402移掉K位数字

单调栈或者字符串解法

目标就是删除几个大的数，但又要维持原来的顺序不改变，字符串是栈解法的高级版本

单调栈

class Solution {
public:
  string removeKdigits(string num, int k) {
	stack<char> s;
	for (int i = 0; i < num.size(); i++)
	{
		while (!s.empty() && s.top() > num[i] && k)
		{
			s.pop();
			k--;
		}
		if (s.empty() && num[i] == '0')
			continue;//跳过前置0
		s.push(num[i]);
	}
	string result;
	while (!s.empty())
	{
		if (k > 0)//当还要再移除数字的时候：从此时单调递增栈的top部删去数字
			k--;
		else if (k == 0)//当不用再移除数字的时候：把字符串取出来到result
			result += s.top();

		s.pop();	
	}
	reverse(result.begin(), result.end());//stl中的reverse函数
	return result == "" ? "0" : result;
}
 
};

字符串

class Solution {
public:
string removeKdigits(string num, int k)
{
	string result;
	for (int i = 0; i < num.size(); i++)
	{
		while (result.size() && k&&result.back() > num[i])
		{
			result.pop_back();
			k--;
		}
		if (result.size() == 0 && num[i] == '0')
			continue;
		result+=num[i];
	}
    while (k > 0 && !result.empty())
	{
		result.pop_back();
		k--;
	}
	return result == "" ? "0" : result;
}
};