[leetcode] 402. Remove K Digits

https://leetcode.com/contest/5/problems/remove-k-digits/

这个题目是花了一些时间的，虽然是medium，但感觉比这次的hard的题目要难。考虑怎么解决，那就从最简单的例子找规律，刚开始的时候是发现一些有趣的性质，比如去k个数字，要是前k个里面包含0，那么就要把0留下，最后自动去除，但是没有0怎么办，无法找到更一般的性质。后来就想，去一位怎么去，然后就变成去k-1位了，这样就很容易了，要去的这个数，一定是从左到右，第一次比它后面的那个数字大的数字，然后考虑如果数字是非递减的怎么办，这时候去掉后面最大的数字。就这样，可以解决所有情况，包括是0的情况。最后输出结果的时候要去掉前面的0.

class Solution {
public:
  string removeKdigits(string num, int k) {
        int n = num.size();
        if(k >= n) {
            return "0";
        }
        while(k) {
            int i = 0;
            bool f = 0;
            for (i = 0; i < num.size() - 1; i++) {
                if(num[i] > num[i + 1]) {
                    f = 1;
                    num = num.erase(i, 1);
                    break;
                }
            }
            if(!f) {
                num = num.substr(0, num.size() - 1);
            }
            k--;
        }
        while(num.size() > 1 && num[0] == '0') num = num.substr(1);
        return num;
    }
};