【LeetCode-402】移掉K位数字
2024-01-07 21:15:42
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;
}
文章来源:https://blog.csdn.net/qq_44426403/article/details/135443006
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!