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: }
No comments:
Post a Comment