LeetCode 402 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.

一句话题意

有一个长度为N的数字，用字符串来表示，现在要求你将它删除K位，使得删除后得到数字的值最小。

解题思路

要使删除后的数字最小，那么就需要高位的数字值越小。这是一种贪心的思想，如果当前数字比前面的小，并且可以删除数字，那么就可以删除前面较大的数字。

具体做法就是哈维持一个递增的序列，队列为空时，将字符串中数字加入队列。其他时候，将当前字符串与队尾元素比较，如果比队列中最后一个元素小，并且还可以继续删除元素，那么就将最后一个元素删掉，再跟新的队尾元素比较。这样可以保证将当前元素加进去一定可以得到一个较小的序列。

最后我们将队列中元素组成一个新的字符串即可，当然，如果得到的是一个空队列那就返回０。

另外还需要注意字符串首字符不能为0