動機
讓前面數字越小越好!!
Problem
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 = 3Output: "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 = 1Output: "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 = 2Output: "0"Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Constraints:
- t
1 <= k <= num.length <= 105
tnum
consists of only digits. tnum
does not have any leading zeros except for the zero itself.
Sol
在保持順序的狀態下,維持某一條件,Monotonic Stack
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stk = []
for c in num:
while stk and k and stk[-1] > c:
stk.pop()
k -= 1
stk.append(c)
for _ in range(k):
if stk:
stk.pop()
i = 0
while i < len(stk) and stk[i] == '0':
i += 1
stk= stk[i:]
return "0" if not stk else ''.join(stk)