402. Remove K Digits
Đề Bài
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
Example 1:
Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Constraints:
1 <= k <= num.length <= 105numconsists of only digits.numdoes not have any leading zeros except for the zero itself.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(1)
Lời Giải
C++
0402-remove-k-digits.cpp
class Solution {
public:
string removeKdigits(string num, int k) {
int n = num.size();
if (n <= k) {
return "0";
}
if (k == 0) {
return num;
}
stack<char> st;
st.push(num[0]);
for (int i = 1; i < n; ++i) {
while (k > 0 and !st.empty() and st.top() > num[i]) {
st.pop();
--k;
}
st.push(num[i]);
if (st.size() == 1 and num[i] == '0') {
st.pop();
}
}
while (k > 0 and !st.empty()) {
st.pop();
--k;
}
string res;
while (!st.empty()) {
res.push_back(st.top());
st.pop();
}
if (res.size() == 0) {
return "0";
}
reverse(res.begin(), res.end());
return res;
}
};
Python
0402-remove-k-digits.py
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for d in num:
while stack and stack[-1] > d and k > 0:
stack.pop()
k -= 1
stack.append(d)
while k > 0:
stack.pop()
k -= 1
i = 0
while i < len(stack) and stack[i] == '0':
i += 1
res = "".join(stack[i:])
return res or "0"