https://leetcode.com/problems/remove-k-digits/
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
- The length of num is less than 10002 and will be ≥ k.
- The given num does not contain any leading zero.
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.
- 用单调栈维护一个递增的序列,发现当前数字比栈顶元素要小的数字就 pop 栈顶
- 如果遍历完整个 string 还有多余的 k(k>0),说明还要再继续 pop,则只需要从栈顶 pop 掉 k 个元素
- 还要处理 leading zero 的情况,只需要从 0 开始遍历栈,若 stack[i] = "0",i++
- 返回处理完 leading zero 之后的栈,如果栈空,那么返回0,表示我们已经 remove 完所有的元素。
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for x in num:
while stack and int(stack[-1]) > int(x) and k:
stack.pop()
k -= 1
stack.append(str(x))
while k:
# all is increasing
stack.pop()
k -= 1
i = 0
while i < len(stack) and stack[i] == "0":
# skip leading zero
i += 1
return "".join(stack[i:]) if len(stack[i:]) > 0 else "0"