Open
Description
习题
给定一个以字符串表示的非负整数 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。
思路
除了第一个数字，对于每个数字，我们都能确定它和它前一个数字的大小，进行比较，留下较小的一个。
解答
javascript
/**
* @param {string} num
* @param {number} k
* @return {string}
*/
var removeKdigits = function(num, k) {
var stack = [];
for (let i = 0, len = num.length; i < len; i++) {
while(k > 0 && stack.length > 0 && stack[stack.length - 1] > num[i]) {
stack.pop();
k--;
}
if (num[i] != '0' || stack.length > 0) {
stack.push(num[i]);
}
}
while(k > 0) {
stack.pop();
k--;
}
return stack.length == 0 ? '0' : stack.join('');
};go
func removeKdigits(num string, k int) string {
stack := make([]rune, 0)
for _, c := range num {
for k > 0 && len(stack) > 0 && stack[len(stack) - 1] > c {
stack = stack[0: len(stack) - 1]
k--
}
if (c != '0' || len(stack) > 0) {
stack = append(stack, c)
}
}
for k > 0 && len(stack) > 0 {
stack = stack[0: len(stack) - 1]
k--
}
if len(stack) == 0 {
return "0"
} else {
return string(stack)
}
}Metadata
Assignees
Labels
No labels