# 402. Remove K Digits

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: string removeKdigits(string num, int k) { if (num.length() == k) return "0"; string ans; vector stack; for (int i = 0; i < num.length(); ++i) { while (k > 0 && !stack.empty() && stack.back() > num[i]) { stack.pop_back(); --k; } stack.push_back(num[i]); } while (k-- > 0) stack.pop_back(); for (const char c : stack) { if (c == '0' && ans.empty()) continue; ans += c; } return ans.empty() ? "0" : ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public String removeKdigits(String num, int k) { if (num.length() == k) return "0"; StringBuilder sb = new StringBuilder(); LinkedList stack = new LinkedList<>(); for (int i = 0; i < num.length(); ++i) { while (k > 0 && !stack.isEmpty() && stack.getLast() > num.charAt(i)) { stack.pollLast(); --k; } stack.addLast(num.charAt(i)); } while (k-- > 0) stack.pollLast(); for (final char c : stack) { if (c == '0' && sb.length() == 0) continue; sb.append(c); } return sb.length() == 0 ? "0" : sb.toString(); } }