【LeetCode-402】移掉K位数字

发布时间:2024年01月07日

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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。