[Leetcode] Remove K Digits, Solution

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.

[Thoughts]

首先分析一下什么样的数是最小的数。数总是有0~9的数字组成，高位的数字越小，这个数就越小。

所以，在对一个数做删除数字处理的时候，首先要从高位上把大的数字干掉，尽可能保留小的。

举个例子 num = "143219", k = 4

这个数字可以按照递增和递减分成三段 “1”， “4321”， “9”。递减子段上除了最后一个数字，其他的都可以被删除。

如果递减子段都处理完了，还没有删满k个，那就从最右边删（因为剩下的都是递增区间段了。）

[Code]

1:    string removeKdigits(string num, int k) {  
2:      string res = "";  
3:        
4:      for(int i =0; i<num.size(); i++) {  
5:        while(res.size()>0 && res.back() > num[i]&& k>0) {  
6:          res.pop_back();  
7:          k--;  
8:        }  
9:        res.push_back(num[i]);  
10:      }  
11:        
12:      // if k != 0, remove the digit from right  
13:      res.erase(res.size() - k, k);  
14:        
15:      // trim the zero  
16:      int i =0;  
17:      while(res[i] == '0' && i<res.size()-1) i++;  
18:        
19:      res.erase(0, i);  
20:        
21:      return res.size() == 0? "0": res;  
22:    }