大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

LeetCoden位数字,移除其中k位,使得结果最小-创新互联

n位数字,移除其中k位,使得结果最小。

原题链接

创新互联服务项目包括怀来网站建设、怀来网站制作、怀来网页制作以及怀来网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,怀来网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到怀来省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!

更新:基本一样的的题目1673. 找出最具竞争力的子序列

C++代码
class Solution {public:
    vectormostCompetitive(vector& nums, int k) {int cnt = nums.size() - k;

        stackstk;
        for(int& x : nums) {while(stk.size() && cnt >0 && stk.top() >x) stk.pop(), cnt -- ;
            stk.push(x);
        }

        while(cnt --) stk.pop();
        vectorres;
        while(stk.size()) res.push_back(stk.top()), stk.pop();
        reverse(res.begin(), res.end());
        return res;
    }
};

文章目录
  • n位数字,移除其中k位,使得结果最小。
    • C++代码
    • 思路
    • 算法(单调栈)
    • 算法复杂度
    • C++代码

思路

不难发现,对于相同前缀的两个数字 34 x 34x 34x和 34 y 34y 34y,如果 x < y x< y x

那我们就可以知道:要求最终的结果最小,那么前缀中的数字要尽可能的小。我们知道“小”是相对的,也就是我们需要来选择这个数中的哪些数字要被保留下来,成为”小“的数字。

我们来考虑这样一种情况,对于下标 i i i上的数字 d i g i t digit digit,如果他左边(下标 < i 算法(单调栈)

到这里我们就需要考虑每一个数字的前面哪些较大的数,并且能够将他们移除(移除的次数 k k k需要大于0),我们可以用一个栈来维护这个数字序列,枚举该序列,假设当前枚举的数字为 x x x,判断栈顶的数字是否大于 x x x,如果大于,则弹出该栈顶元素,继续执行该过程,直到①栈中不存在数字_或者_②栈顶的数字不大于 x x x_或者_③ k = = 0 k == 0 k==0 这些情况的出现,接着我们将当前元素添加到栈中。

到这里我们需要来解释一下为什么只有栈顶的数字大于 x x x才考虑移除栈中的元素。

  • 首先我们考虑栈顶元素小于当前元素的情况,如果我们选择移除栈顶元素,那么数字序列的前缀将变大,不符合题目要求,所以我们不应该移除栈顶元素。

  • 如果当前元素等于栈顶元素,我们考虑紧接着要枚举到的元素 y y y,如果 x < y x< y x y x >y x>y,那么我们执行上一段中:

    判断栈顶的数字是否大于 x x x,如果大于,则弹出该栈顶元素。

    即可。

算法复杂度

时间复杂度: O ( n ) O(n) O(n),n为数字序列的长度,每个数字至多会被 p u s h ( ) push() push()和 p o p ( ) pop() pop()一次。

空间复杂度: O ( n ) O(n) O(n),n为数字序列的长度。

C++代码
class Solution {public:
    string removeKdigits(string num, int k) {stackstk;
        for(auto& c : num) {int x = c - '0';
            while(stk.size() && k >0 && stk.top() >x) {stk.pop();
                k -- ;
            }
            stk.push(x);
        }

        while(k --) stk.pop();
        string res;
        while(stk.size()) res += stk.top() + '0', stk.pop();
        while(res.size() >1 && res.back() == '0') res.pop_back();
        if(res.size() == 0) res = '0';
        reverse(res.begin(), res.end());
        return res;
    }
};

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前标题:LeetCoden位数字,移除其中k位,使得结果最小-创新互联
分享链接:http://dzwzjz.com/article/dciihs.html
在线咨询
服务热线
服务热线:028-86922220
TOP