Leetcode-402Remove K Digits

402. Remove K Digits

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.

题解：

非负整数num，移除num中的k个数字后，求所能得到的最小的数是多少；
输入的是一个字符串表示的num和要去除的数字的个数k：
例如题中所给的例1：
输入: num = "1432219", k = 3
1432219去除3个数字后得到的最小的数为1219；
输出: "1219"

分析：

如何能够保证删除数字后所得到的数最小呢？
不难想到，最小的数，它的最高位一定要尽可能的取最小的，次高位尽可能的取最高位后面最小的，直到删除的数的个数为k为止；
以num = "1432219", k = 3为例：

1. 考虑第一位数字1，分为两种可能：
   删除1：（1）432219 ：删除1的话我们可以得到432219；
   不删除1：1 （432219）：不删除1的话我们需要在432219中删除一个数字；
   不难看出，无论后续删除432219中的哪个数字，1xxxxx 始终小于 432219；所以保留1为最优策略。
2. 考虑第二位数字4，分为两种可能：
   删除4：1（4）32219 ：删除4的话我们可以得到132219；
   不删除4：14（32219）：不删除4的话我们需要在32219中删除一个数字；
   不难看出，无论后续删除32219中的哪个数字，132219始终小于14xxxx；所以删除4为最优策略。因为删除了数字4，所以此时的k = k - 1 = 2；
3. 考虑第三位数字3，分为两种可能：
   删除3：1（3）2219 ：删除3的话我们可以得到12219；
   不删除3：13（2219）：不删除4的话我们需要在2219中删除一个数字；
   不难看出，无论后续删除2219中的哪个数字，12219始终小于13xxx；所以删除3为最优策略。因为删除了数字3，所以此时的k = k - 1 = 1；
4. 考虑第四位数字2，分为两种可能：
   删除2：1（2）219 ：删除2的话我们可以得到1219；
   不删除2：12（219）：不删除2的话我们需要在219中删除一个数字；
   发现我们没办法判断12xx和1219谁比较大；所以暂时保留2等待后续的判断为最优策略；
5. 考虑第五位数字2，分为两种可能：
   删除2：12（2）19 ：删除2的话我们可以得到1219；
   不删除2：122（19）：不删除2的话我们需要在19中删除一个数字；
   不难看出，无论后续删除19中的哪个数字，1219始终小于122x；所以删除2为最优策略。因为删除了数字3，所以此时k = k - 1 = 0；
   截止到这里，我们成功的删除了3个数字，所以最后输出结果1219。
   那么如果k=4的时候呢？
   前五步依然一样，我们得到了1219，而此时的k=1；我们需要再删除一个数；
   可能看到上面的分析过程我们会惯性的认为，接下来，我们应该考虑第六位数字1，因为保留1的时候121<129，所以保留1，删除9，最后输出121；
   其实不然，正确的答案明显是119，第六步直接考虑第六位是错误的！
   我们忽略了我们要取最优策略，应该尽可能的让最高位取最小值，次高位取第二小的值，直到k=0；所以正确的第六步应该是在删除了第五位数字2以后，考虑第四位的2是否应该删除；
   所以进展到1219，k=1时，我们给出正确的第六步比较：
6. 考虑第四位数字2（以保留的数字中最后一位），分为两种可能：
   删除2：1（2）19 ：删除2的话我们可以得到119；
   不删除2：12（19）：不删除2的话我们需要在19中删除一个数字；
   不难看出，无论后续删除19中的哪个数字，119始终小于12x；所以删除2为最优策略。因为删除了数字2，所以此时k = k - 1 = 0；
   如何用程序来实现这个过程呢？
   上述的分析，我们发现，如果我们创建一个数组专门用来存储要保留的数字；为了保证保留的数的最高位是最小的，次高位第二小...我们需要保证数组中的数以递增的方式存储；
   当前的数字则需要对数组中的数由高到低依次比较，只要当前的数字小于数组中最后的数字，我们就将数组中最后的数字删除（k-1）；
   然后再拿当前的数字和新的数组中的数字进行比较，直到k=0或者当前的数字大于数组中最后的数字时，保留当前的数字；
   因为这个数组的元素满足递增顺序所以在和当前数字比较的时候，相当于先进后比较；满足栈的数据结构，所以我们用栈来模拟下存储的过程：
   image.png
   image.png
   如果操作结束以后k>0或者数字0是最高位的时候呢？
   image.png
7. 结束以后k>0：取前 stack.size() - k 个数字即可；
8. 者数字0是最高位：栈为空时，遇见数字0，不把0压入栈即可~；
   最后我们给出代码实现，这里我们用vector容器来代替stack存储保留的数字；因为vector容器可以遍历，更方便一些；

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <string>  // 标准c++库，cout重载的是string类库的string类型；不是cstring或string.h，后者是C语言里面关于字符数组的函数定义的头文件；
#include <vector>

using namespace std;

class Solution {
public:
    string removeKdigits(string num, int k) {
        string result = "";
        vector<int> mems;
        for (int i = 0; i < num.length(); i++) {
            int mem = num[i] - '0';
            if (k != 0) {
                while (!mems.empty() && mem < mems[mems.size() - 1]) {
                    mems.pop_back();
                    k -= 1;
                    if (k == 0) {
                        break;
                    }
                }
                if (!mems.empty() || mem != 0) {
                    mems.push_back(mem);
                }
            }
            else {
                mems.push_back(mem);
            }
        }
        int len = mems.size();
        if (k != 0) {
            len = len - k;
        }
        for (int i = 0; i < len; i++) {
            result.append(1, mems[i] + '0');  //在result后面添加一个字符；
        }
        if (result == "") {
            return "0";  //注意返回值类型为string，不能return 0或者return '0'；
        }
        return result;
    }
};

int main() {
    Solution s;
    cout << s.removeKdigits("1432219", 4);
    getchar();
    return 0;
}

结果：

119`

My Solution（Python）:

class Solution:
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        tem_stack = []
        nums = list(num)
        # if len(nums) == k:
        #     return '0'
        # if len(nums) == 1:
        #     return num
        for i in range(len(nums)):
            if tem_stack == []:
                tem_stack.append(nums[i])
            elif nums[i] >= tem_stack[-1]:
                tem_stack.append(nums[i])
            while nums[i] < tem_stack[-1]:
                tem_stack.pop()
                k -= 1
                if k == 0:
                    tem_stack.append(nums[i])
                    break
                if tem_stack == [] or nums[i] >= tem_stack[-1]:
                    tem_stack.append(nums[i])
            if k == 0:
                tem_stack += nums[i+1:]
                break
        # for j in range(len(tem_stack)):
        #     if tem_stack[j] != '0':
        return ''.join(tem_stack[ :len(tem_stack) - k]).lstrip('0') or '0'

Reference:

class Solution:
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        out=[]
        for digit in num:
            while k and out and out[-1] > digit:
                out.pop()
                k-=1
            out.append(digit)
        return ''.join(out[:-k or None]).lstrip('0') or "0"