402. Remove the K digits

Title description:

Given a non-negative integer num represented as a string, remove the k digits from the number to minimize the remaining digits.

Example 1:
Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form a new minimum number 1219.Copy the code
Example 2:
Input: num = "10200", k = 1 Output: "200" Explanation: Remove the first 1 and the remaining number is 200. Note that the output cannot have any leading zeros.Copy the code
Example 3:
Input: num = "10", k = 2 Output: "0" Description: Remove all digits from the original number.Copy the code
Note:
The length of num is less than 10002 and ≥ K. Num will not contain any leading zeros.Copy the code

Directions: For this part,

This is a medium difficulty problem in the stack series, and it’s easy to understand if you look closely at the examples in the problem.

Here’s the greedy stack algorithm:

Because we need to get rid of a certain digit to get to the minimum. So it needs to be noted that we should make the new number as small as possible, the first highest digit is the smallest, the second highest digit is the smallest, the third digit is the smallest… Cycle through. Next comes the greedy algorithm part: the highest to the lowest traversal, if the corresponding digit is larger than the next digit, then the digit is removed, the smallest number. So if you want to get rid of K digits, you just iterate K times from the highest digit. And then finally, the special case of zero.

Let’s look at the solution implementation:

Code implementation:

func removeKdigits(num string, K int) string {var result []byte for I := range num {c := num[I] // Maintain monotone non-decreasing for k > 0 && len(result) > 0 && result[len(result)-1] > c { result = result[:len(result)-1] k-- } result = append(result, C)} result = result[:len(result)-k] "0") // Handle special case of "00000xxx" if s == "{return "0"} return s}Copy the code

Conclusion:

The problem of removing K digits is not too difficult, and the implementation code is also very simple. It is not difficult to solve the problem as long as you understand the meaning of the problem clearly. It is worth noting that the extreme value problem of the boundary is dealt with, and the special case where the result is zero.