class Solution {
public:
string removeKdigits(string num, int k) {
}
};
402. 移掉 K 位数字
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 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 。
提示：
1 <= k <= num.length <= 105num 仅由若干位数字（0 - 9）组成num 不含任何前导零原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 4.5 MB, 提交时间: 2023-07-23 10:35:05
func removeKdigits(num string, k int) string {
stack := []byte{}
for i := range num {
digit := num[i]
for k > 0 && len(stack) > 0 && digit < stack[len(stack)-1] {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, digit)
}
stack = stack[:len(stack)-k]
ans := strings.TrimLeft(string(stack), "0")
if ans == "" {
ans = "0"
}
return ans
}
python3 解法, 执行用时: 68 ms, 内存消耗: 17.6 MB, 提交时间: 2023-07-23 10:34:54
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
numStack = []
# 构建单调递增的数字串
for digit in num:
while k and numStack and numStack[-1] > digit:
numStack.pop()
k -= 1
numStack.append(digit)
# 如果 K > 0，删除末尾的 K 个字符
finalStack = numStack[:-k] if k else numStack
# 抹去前导零
return "".join(finalStack).lstrip('0') or "0"
javascript 解法, 执行用时: 68 ms, 内存消耗: 47.2 MB, 提交时间: 2023-07-23 10:34:40
/**
* @param {string} num
* @param {number} k
* @return {string}
*/
var removeKdigits = function(num, k) {
const stk = [];
for (const digit of num) {
while (stk.length > 0 && stk[stk.length - 1] > digit && k) {
stk.pop();
k -= 1;
}
stk.push(digit);
}
for (; k > 0; --k) {
stk.pop();
}
let ans = "";
let isLeadingZero = true;
for (const digit of stk) {
if (isLeadingZero && digit === '0') {
continue;
}
isLeadingZero = false;
ans += digit;
}
return ans === "" ? "0" : ans;
};
java 解法, 执行用时: 11 ms, 内存消耗: 43.2 MB, 提交时间: 2023-07-23 10:34:24
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> deque = new LinkedList<Character>();
int length = num.length();
for (int i = 0; i < length; ++i) {
char digit = num.charAt(i);
while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
deque.pollLast();
k--;
}
deque.offerLast(digit);
}
for (int i = 0; i < k; ++i) {
deque.pollLast();
}
StringBuilder ret = new StringBuilder();
boolean leadingZero = true;
while (!deque.isEmpty()) {
char digit = deque.pollFirst();
if (leadingZero && digit == '0') {
continue;
}
leadingZero = false;
ret.append(digit);
}
return ret.length() == 0 ? "0" : ret.toString();
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 8.8 MB, 提交时间: 2023-07-23 10:34:04
/**
* 贪心 + 单调栈
* 若要使得剩下的数字最小，需要保证靠前的数字尽可能小
**/
class Solution {
public:
string removeKdigits(string num, int k) {
vector<char> stk;
for (auto& digit: num) {
while (stk.size() > 0 && stk.back() > digit && k) {
stk.pop_back();
k -= 1;
}
stk.push_back(digit);
}
for (; k > 0; --k) {
stk.pop_back();
}
string ans = "";
bool isLeadingZero = true;
for (auto& digit: stk) {
if (isLeadingZero && digit == '0') {
continue;
}
isLeadingZero = false;
ans += digit;
}
return ans == "" ? "0" : ans;
}
};