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）432219 ：删除1的话我们可以得到432219；
不删除1：1 （432219）：不删除1的话我们需要在432219中删除一个数字；
不难看出，无论后续删除432219中的哪个数字，1xxxxx 始终小于 432219；所以保留1为最优策略。 - 考虑第二位数字4，分为两种可能：
删除4：1（4）32219 ：删除4的话我们可以得到132219；
不删除4：14（32219）：不删除4的话我们需要在32219中删除一个数字；
不难看出，无论后续删除32219中的哪个数字，132219始终小于14xxxx；所以删除4为最优策略。因为删除了数字4，所以此时的k = k - 1 = 2； - 考虑第三位数字3，分为两种可能：
删除3：1（3）2219 ：删除3的话我们可以得到12219；
不删除3：13（2219）：不删除4的话我们需要在2219中删除一个数字；
不难看出，无论后续删除2219中的哪个数字，12219始终小于13xxx；所以删除3为最优策略。因为删除了数字3，所以此时的k = k - 1 = 1； - 考虑第四位数字2，分为两种可能：
删除2：1（2）219 ：删除2的话我们可以得到1219；
不删除2：12（219）：不删除2的话我们需要在219中删除一个数字；
发现我们没办法判断12xx和1219谁比较大；所以暂时保留2等待后续的判断为最优策略； - 考虑第五位数字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时，我们给出正确的第六步比较： - 考虑第四位数字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 - 结束以后k>0：取前 stack.size() - k 个数字即可；
- 者数字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"
