1、题目描述
【题目链接】
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 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 。
提示：
1 <= k <= num.length <= 105
num 仅由若干位数字（0 - 9）组成
除了 0 本身之外，num 不含任何前导零
2、基本思路
【贪心+单调栈】
对于一串数字字符串，在移除这个数中的 k 位数字后，使得剩下的数字最小，只需要保证高位的数字要尽可能地小，换句话说，剩下的数字字符串是一个单调不减的序列。
比如所给的示例1，字符串为”1432219“，移除这个数中的3位数字：
- 初始数据结构为空；
- 首先，从第一位开始扫描，结果为 ”1“，先保存在数据结构中：“1”；
- 第二位为”4“，”4“比存放的数字”1“要大，保存在数据结构中：“14”；
- 第三位为”3“，”3“明显比”4“要小，删除高位的”4“换成3，会使数字变小，所以删除”4“，数据结构中：“1”；
- 继续与数据结构中的数字继续比较，“3”要比“1”大，删除“1”并不能保证会使数字变小，则停止删除，并将3保存，数据结构中：“13”。
以此类推，直到删除3次，并将剩余的字符串依次保存。最后数据结构中的数字序列即为答案1219。
上述的数据结构，我们可以采用栈的结构，维护一个单调不减的单调栈：
对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到
- 栈为空
- 或者新的栈顶元素不大于当前数字
- 或者我们已经删除了 k 位数字
我们还需要额外主义三种情况：
- 特殊情况1
删除的数字个数 m < k,需要从序列尾部删除额外的k-m个数 - 特殊情况2
最终的数字含有前导0,需要删除前导0 - 特殊情况3
如果最终的序列为空,我们应该返回0，例如示例3
3、代码实现
string solve(string num,int k)
{
/*
若要使得剩下的数字最小，需要保证靠前的数字尽可能小。
要想移除k位数字后，使得剩下的数字最小，要保证
高位数字要尽可能得小；
从左往右维护一个单调递增(单调不降 <= )的序列
*/
int n = num.length();
stack<char> st;
int cnt = 0;
for(int i = 0;i<n;i++)
{
int c = num[i];
while(!st.empty() && st.top()>c && cnt!=k)
{
cnt++;
st.pop();
}
st.push(c);
}
//特殊情况1
//删除的数字个数 m < k,需要从序列尾部删除额外的k-m个数
while(k-cnt>0)
{
st.pop();
cnt++;
}
//特殊情况2
//最终的数字含有前导0,需要删除前导0
string a;
while(!st.empty())
{
a+=st.top();
st.pop();
}
//栈中的元素顺序为逆序，需要取逆序得到正序的数字串序列
reverse(a.begin(), a.end());
int flag = true;
int j =0;
string b;
for(int i = 0;i<a.size();++i)
{
if(flag==true&&a[i]=='0')
continue;
flag = false;
b += a[i];
}
//特殊情况3
//如果最终的序列为空,我们应该返回0
return b==""? "0": b;
}
