Delete Digits

Problem Description

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. Find the smallest integer after remove k digits.

N <= 240 and k <= N

Example

Given an integer A = "178542", k = 4 return a string "12"

Problem Link

Solution

It is evident that smaller digits should be moved forward as far as they can. In order to implement this intuition, we maintain a non-decreasing stack.

Both time complexity and space complexity are O(n) where n is the number of digits.

public class Solution {
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    public String DeleteDigits(String num, int k) {
        // write your code here
        int n = num.length(), m = n - k;
        vector<int> st(n); int top = 0;
        for (int i = 0; i < n; ++ i) {
            while (top > 0 && k > 0 && num[st[top - 1]] > num[i]) {
                -- top;
                -- k;
            }
            st[top ++] = i;
        }

        string ans = ""; bool flag = false;
        for (int i = 0; i < top && i < m; ++ i) {
            if (!flag && num[st[i]] == '0') continue;
            flag = true;
            ans.push_back(num[st[i]]);
        }

        if (ans.length() == 0) ans = "0";
        return ans;
    }
}