402. Remove K Digits

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: num = "1432219", k = 3 Output: "1219"

Input: num = "10200", k = 1 Output: "200"

Input: num = "10", k = 2 Output: "0"

Solution Approach

Using a monotonic stack to simulate the process of removing digits while ensuring the resulting number is minimized.

Algorithm

1. Initialize a stack to store digits and add the first digit from num.
2. Iterate through the remaining digits in num, maintaining a monotonic decreasing stack.
3. While the stack is not empty, the top digit is greater than the current digit, and there are still removals (k > 0), pop elements from the stack until the conditions are met or the removal limit is reached.
4. Append the current digit to the stack.
5. If there are remaining removals (k > 0) after iterating through num, remove the required number of elements from the end of the stack.
6. Concatenate the digits in the stack, remove leading zeros, and return the resulting string, or “0” if the string is empty.

Implement

    class Solution:
    def removeKdigits(self, num:str, k:int):
      stack = [nums[0]]
      for i in range(1, len(num)):
        while stack and int(stack[-1]) > num[i] and k > 0:
          stack.pop()
          k -= 1
        stack.append(num[i])
      if k > 0:
        stack = stack[-k]
      return "".join(stack).lstrip("0") or "0"

       

    
    

Twitter  facebook  Email