A greedy method using stack, O(n) time and O(n) space
~~~~\npublic class Solution {\n    public String removeKdigits(String num, int k) {\n        int digits = num.length() - k;\n        char[] stk = new char[num.l
~~~~\npublic class Solution {\n    public String removeKdigits(String num, int k) {\n        int digits = num.length() - k;\n        char[] stk = new char[num.length()];\n        int top = 0;\n        // k keeps track of how many characters we can remove\n        // if the previous character in stk is larger than the current one\n        // then removing it will get a smaller number\n        // but we can only do so when k is larger than 0\n        for (int i = 0; i < num.length(); ++i) {\n            char c = num.charAt(i);\n            while (top > 0 && stk[top-1] > c && k > 0) {\n                top -= 1;\n                k -= 1;\n            }\n            stk[top++] = c;\n        }\n        // find the index of first non-zero digit\n        int idx = 0;\n        while (idx < digits && stk[idx] == '0') idx++;\n        return idx == digits? "0": new String(stk, idx, digits - idx);\n    }\n}\n~~~~
[]