生活随笔
收集整理的这篇文章主要介绍了
LeetCode 402. 移掉K位数字（贪心，单调栈）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
1. 题目
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例
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。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-k-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 单调栈
class Solution {
public:string
removeKdigits(string num
, int k
) {if(k
==num
.size())return "0";char m
;int len
= num
.size()-k
, i
;string s
;for(i
= 0; i
< num
.size(); ++i
){m
= num
[i
];while(!s
.empty() && s
.back() > m
&& k
){s
.pop_back();k
--;}if(k
== 0)break;s
.push_back(m
);}if(k
== 0)s
= s
+ num
.substr(i
); while(s
.size() != len
)s
.pop_back();while(s
.size()>1 && s
[0]=='0')s
.erase(0,1);return s
;}
};
class Solution {
public:string
removeKdigits(string num
, int k
) {string ans
;for(int i
= 0; i
< num
.size(); ++i
){while(!ans
.empty() && ans
.back() > num
[i
] && k
> 0){ans
.pop_back();k
--;}ans
.push_back(num
[i
]);}while(k
--)ans
.pop_back();int i
= 0;while(i
< ans
.size() && ans
[i
] == '0')i
++;ans
= ans
.substr(i
);return ans
=="" ? "0" : ans
;}
};
创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖
总结
以上是生活随笔为你收集整理的LeetCode 402. 移掉K位数字（贪心，单调栈）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
