Delete Digits

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"

------------------------------ thinking -----------------------------------
This is quite like calculating the biggest area of histogram, we need to keep a increasing array by using stack
------------------------------ codes -------------------------------------
class Solution {
public:
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    string DeleteDigits(string A, int k) {
        // wirte your code here
        stack<int> stk;
        stk.push(0);
        int i = 1;
        while (k > 0) {
            if (i < A.size()) {
                if (stk.empty() || A[i] >= A[stk.top()]) {
                    stk.push(i);
                    i++;
                } else {
                    stk.pop();
                    k--;
                }
            } else {
                stk.pop();
                k--;
            }
        }
        string result = A.substr(i, A.size() - i);
        while (!stk.empty()) {
            result = A.substr(stk.top(), 1) + result;
            stk.pop();
        }
        while (result.size() > 1 && result[0] == '0') {
            result.erase(0, 1);
        }
        return result;
    }
};