LeetCoden位数字,移除其中k位,使得结果最小-创新互联
原题链接
创新互联服务项目包括怀来网站建设、怀来网站制作、怀来网页制作以及怀来网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,怀来网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到怀来省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!C++代码更新:基本一样的的题目1673. 找出最具竞争力的子序列
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 判断栈顶的数字是否大于
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为数字序列的长度。 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
算法复杂度class Solution {public:
string removeKdigits(string num, int k) {stack
新闻标题:LeetCoden位数字,移除其中k位,使得结果最小-创新互联
标题路径:http://pwwzsj.com/article/dciihs.html