前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的402题。
问题描述
给定一个以字符串表示的非负整数 num，移除这个数中的 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。
分析：
贪心
其基本思想是利用栈尽量维持一个递增的序列，也就是说将字符串中字符依次入栈，如果当前字符串比栈顶元素小，并且还可以继续删除元素，那么就将栈顶元素删掉，这样可以保证将当前元素加进去一定可以得到一个较小的序列．也可以算是一个贪心思想．最后我们只取前len-k个元素构成一个序列即可，如果这样得到的是一个空串那就手动返回０．还有一个需要注意的是字符串首字符不为０
func removeKdigits(num string, k int) string {
l := len(num)
n := k
stack := make([]byte, 0)
for i := 0; i < l; i++ {
for len(stack) != 0 && n > 0 && num[i] < stack[len(stack)-1] {
stack = stack[:len(stack)-1]
n--
}
stack = append(stack, num[i])
}
cnt := 0
for cnt < len(stack) && stack[cnt] == '0' {
cnt++
}
fmt.Println(n, len(stack))
if cnt == len(stack) || cnt == len(stack)-n {
return "0"
}
return string(stack[cnt:len(stack)-n])
}
C++
class Solution {
public:
string removeKdigits(string num, int k) {
string ans;
int n = k, len = num.size(), cnt = 0;
for(auto val: num)
{
while(!ans.empty() && n > 0 && val < ans.back())
{
n--;
ans.pop_back();
}
ans.push_back(val);
}
while(ans[cnt]=='0') cnt++;
ans = ans.substr(cnt, len-k-cnt);
return !ans.size()?"0":ans;
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
