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.
題解：
非負(fù)整數(shù)num，移除num中的k個數(shù)字后移迫，求所能得到的最小的數(shù)是多少；
輸入的是一個字符串表示的num和要去除的數(shù)字的個數(shù)k：
例如題中所給的例1：
輸入: num = "1432219", k = 3
1432219去除3個數(shù)字后得到的最小的數(shù)為1219运准；
輸出: "1219"
分析：
如何能夠保證刪除數(shù)字后所得到的數(shù)最小呢利职？
不難想到违诗，最小的數(shù)牧牢，它的最高位一定要盡可能的取最小的揖膜，次高位盡可能的取最高位后面最小的誓沸，直到刪除的數(shù)的個數(shù)為k為止；
以num = "1432219", k = 3為例：
- 考慮第一位數(shù)字1壹粟，分為兩種可能：
刪除1：（1）432219 ：刪除1的話我們可以得到432219拜隧；
不刪除1：1 （432219）：不刪除1的話我們需要在432219中刪除一個數(shù)字；
不難看出趁仙，無論后續(xù)刪除432219中的哪個數(shù)字洪添，1xxxxx 始終小于 432219；所以保留1為最優(yōu)策略雀费。 - 考慮第二位數(shù)字4，分為兩種可能：
刪除4：1（4）32219 ：刪除4的話我們可以得到132219盏袄；
不刪除4：14（32219）：不刪除4的話我們需要在32219中刪除一個數(shù)字忿峻；
不難看出，無論后續(xù)刪除32219中的哪個數(shù)字辕羽，132219始終小于14xxxx炭菌；所以刪除4為最優(yōu)策略。因為刪除了數(shù)字4逛漫，所以此時的k = k - 1 = 2黑低； - 考慮第三位數(shù)字3，分為兩種可能：
刪除3：1（3）2219 ：刪除3的話我們可以得到12219酌毡；
不刪除3：13（2219）：不刪除4的話我們需要在2219中刪除一個數(shù)字克握；
不難看出，無論后續(xù)刪除2219中的哪個數(shù)字枷踏，12219始終小于13xxx菩暗；所以刪除3為最優(yōu)策略。因為刪除了數(shù)字3旭蠕，所以此時的k = k - 1 = 1停团； - 考慮第四位數(shù)字2旷坦，分為兩種可能：
刪除2：1（2）219 ：刪除2的話我們可以得到1219；
不刪除2：12（219）：不刪除2的話我們需要在219中刪除一個數(shù)字佑稠；
發(fā)現(xiàn)我們沒辦法判斷12xx和1219誰比較大秒梅；所以暫時保留2等待后續(xù)的判斷為最優(yōu)策略； - 考慮第五位數(shù)字2舌胶，分為兩種可能：
刪除2：12（2）19 ：刪除2的話我們可以得到1219捆蜀；
不刪除2：122（19）：不刪除2的話我們需要在19中刪除一個數(shù)字；
不難看出幔嫂，無論后續(xù)刪除19中的哪個數(shù)字辆它，1219始終小于122x；所以刪除2為最優(yōu)策略履恩。因為刪除了數(shù)字3锰茉，所以此時k = k - 1 = 0；
截止到這里切心，我們成功的刪除了3個數(shù)字洞辣，所以最后輸出結(jié)果1219。
那么如果k=4的時候呢昙衅？
前五步依然一樣，我們得到了1219定鸟，而此時的k=1而涉；我們需要再刪除一個數(shù)；
可能看到上面的分析過程我們會慣性的認(rèn)為联予，接下來啼县，我們應(yīng)該考慮第六位數(shù)字1，因為保留1的時候121<129沸久，所以保留1季眷，刪除9，最后輸出121卷胯；
其實不然子刮，正確的答案明顯是119，第六步直接考慮第六位是錯誤的窑睁！
我們忽略了我們要取最優(yōu)策略挺峡，應(yīng)該盡可能的讓最高位取最小值，次高位取第二小的值担钮，直到k=0橱赠；所以正確的第六步應(yīng)該是在刪除了第五位數(shù)字2以后，考慮第四位的2是否應(yīng)該刪除箫津；
所以進(jìn)展到1219狭姨，k=1時宰啦，我們給出正確的第六步比較： - 考慮第四位數(shù)字2（以保留的數(shù)字中最后一位），分為兩種可能：
刪除2：1（2）19 ：刪除2的話我們可以得到119饼拍；
不刪除2：12（19）：不刪除2的話我們需要在19中刪除一個數(shù)字赡模；
不難看出，無論后續(xù)刪除19中的哪個數(shù)字惕耕，119始終小于12x纺裁；所以刪除2為最優(yōu)策略。因為刪除了數(shù)字2司澎，所以此時k = k - 1 = 0欺缘；
如何用程序來實現(xiàn)這個過程呢？
上述的分析挤安，我們發(fā)現(xiàn)谚殊，如果我們創(chuàng)建一個數(shù)組專門用來存儲要保留的數(shù)字；為了保證保留的數(shù)的最高位是最小的蛤铜，次高位第二小...我們需要保證數(shù)組中的數(shù)以遞增的方式存儲嫩絮；
當(dāng)前的數(shù)字則需要對數(shù)組中的數(shù)由高到低依次比較，只要當(dāng)前的數(shù)字小于數(shù)組中最后的數(shù)字围肥，我們就將數(shù)組中最后的數(shù)字刪除（k-1）剿干；
然后再拿當(dāng)前的數(shù)字和新的數(shù)組中的數(shù)字進(jìn)行比較，直到k=0或者當(dāng)前的數(shù)字大于數(shù)組中最后的數(shù)字時穆刻，保留當(dāng)前的數(shù)字置尔；
因為這個數(shù)組的元素滿足遞增順序所以在和當(dāng)前數(shù)字比較的時候，相當(dāng)于先進(jìn)后比較氢伟；滿足棧的數(shù)據(jù)結(jié)構(gòu)榜轿，所以我們用棧來模擬下存儲的過程：
image.png
image.png
如果操作結(jié)束以后k>0或者數(shù)字0是最高位的時候呢？
image.png - 結(jié)束以后k>0：取前 stack.size() - k 個數(shù)字即可朵锣；
- 者數(shù)字0是最高位：棧為空時谬盐，遇見數(shù)字0，不把0壓入棧即可~诚些；
最后我們給出代碼實現(xiàn)飞傀，這里我們用vector容器來代替stack存儲保留的數(shù)字；因為vector容器可以遍歷诬烹，更方便一些助析；
My Solution（C/C++完整實現(xiàn)）：
#include <cstdio>
#include <iostream>
#include <string> // 標(biāo)準(zhǔn)c++庫，cout重載的是string類庫的string類型椅您；不是cstring或string.h外冀，后者是C語言里面關(guān)于字符數(shù)組的函數(shù)定義的頭文件；
#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;
}
結(jié)果：
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"
