[LintCode] Delete Digits

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer. Make this new positive integers as small as possible.

N <= 240 and k <= N,

Example

Given an integer A="178542", k=4

return a string "12"

http://www.lintcode.com/en/problem/delete-digits/

可能一开始想到的是DFS暴力枚举，但是N大小为240显然暴力的方法并不可取。仔细想想发现其实还是很容易找到规律的，想让一个数字尽可能小，那么就要把小的数字尽量放到前面，如果前面有比它大的数字，那么就到把在它前面且比它大的数字都要删除掉，直到已经删掉k个数字。剩下的就是一些特殊情况与边界情况了，比如前置0要去掉，如果遍历一遍发现删除的数字还不足k个，那么就把最后的k-cnt个删除掉。下面是AC的代码。

 1 class Solution {
 2 public:
 3     /**
 4      *@param A: A positive integer which has N digits, A is a string.
 5      *@param k: Remove k digits.
 6      *@return: A string
 7      */
 8     string DeleteDigits(string A, int k) {
 9         // wirte your code here
10         string s;
11         if (k > A.size()) return s;
12         int cnt = 0;
13         for (int i = 0; i < A.size(); ++i) {
14             while (!s.empty() && s.back() > A[i] && cnt < k) {
15                 s.pop_back();
16                 ++cnt;
17             }
18             if (A[i] != '0' || !s.empty()) s.push_back(A[i]);
19         }
20         if (cnt < k) s.resize(s.size() - k + cnt);
21         return s;
22     }
23 };

[LintCode] Delete Digits

推荐阅读