402. Remove K Digits

怼烎@ 2022-03-21 09:05 115阅读 0赞

Given a non-negative integer *num* represented as a string, remove *k* digits from the number so that the new number is the smallest possible.

**Note:**

*  The length of *num* is less than 10002 and will be ≥ *k*.
 *  The given *num* does not contain any leading zero.

**Example 1:**

Input: num = "1432219", k = 3
    Output: "1219"
    Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

**Example 2:**

Input: num = "10200", k = 1
    Output: "200"
    Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

**Example 3:**

Input: num = "10", k = 2
    Output: "0"
    Explanation: Remove all the digits from the number and it is left with nothing which is 0.

题意：移除K个数字，已知一个**字符串**表示的**非负整数num**，将num中的**K个数字**移除，求移除K个数字后，可以获得的**最小的**数字。

分析：若去掉某一位数字，为了使得到的新数字最小，需要**尽可能**的让新数字**优先最高位**最小，其次次高位最小，以此类推。所以，从**高位向低位**遍历，如果对应的数字**大于**下一位数字，则把该位数字去掉，得到的数字**最小**。

算法：使用**栈**存储最终结果，从**高位向低位**遍历num，如果遍历的数字**大于**栈顶元素，则将该数字**入栈**，如果小于栈顶元素则栈顶元素**出栈**，直到栈为空（size==0）或者不能再删除数字（k==0）或者栈顶小于当前元素为止。由于最后需要输出字符串，我们用vector模拟栈的后进先出效果，并遍历vector得到最终的字符串。

思考：当所有数字都扫描完成后，**K仍然>0**，应该做怎样的处理？当数字中有0出现时，应该有怎样的处理？

class Solution {
    public:
      string removeKdigits(string num, int k) {
    	if (num.size() <= k)
    		return "0";
    
    	vector<char> log;
    	int pos = 0;
    	while (pos < num.size())
    	{
    		if (num[pos] != '0' || !log.empty())
    		{
    			log.push_back(num[pos]);
    		}
    		pos++;
    		while(k>0 && !log.empty() &&num[pos] < log[log.size()-1])
    		{
    			log.pop_back();
    			k--;
    		}	
    	}
    
    	while (k > 0)
    	{
    		log.pop_back();
    		k--;
    	}
    
    	string result;
    	for (int i = 0; i < log.size(); i++)
    	{
    		result += log[i];
    	}
    	if (result == "")
    		result = "0";
    	return result;
    
    }
    };