博客

题目描述

给定一个以字符串表示的非负整数

num

，移除这个数中的

k

位数字，使得剩下的数字最小。

注意

• 
  num
  
  的长度小于 10002 且 ≥
  
  k。
  
• 
  num
  
  不会包含任何前导零。

示例1

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例2

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例3

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

思路

单调栈，这里是单调递增栈，不符合建栈条件的数移除，直到移除k个数，若单调栈建完了还没有移够K个数，则从栈尾开始移除，因为此时栈尾的数最大，直到移够K个数，注意最后的结果开头可能是0，移除结果开头所有的0.

实现

string removeKdigits(string num, int k) {
	stack<char> data;

	for (int i = 0; i < num.length(); i++)
	{
		if (data.empty())
		{
			data.push(num[i]);
		} else {
			while (!data.empty() && num[i] < data.top())
			{
				if (k == 0)
				{
					break;
				}
				data.pop();
				k--;
			}

			data.push(num[i]);
			
		}
	}

	string res;
	while (!data.empty())
	{
		res += data.top();
		data.pop();
	}
	reverse(res.begin(), res.end());

	int index = 0;
	while (res.length() > 0 && res[index] == '0') {
		index++;
	}

	res = res.substr(index);

	if (k <= res.length())
	{
		res = res.substr(0, res.length() - k);
	}
    
    if (res.length() == 0)
	{
		res = "0";
	}

	return res;
}