1255. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.

Have you met this question in a real interview?  

Example

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

class Solution { public: /** * @param num: a string * @param k: an integer * @return: return a string */ string removeKdigits(string &num, int k) { // write your code here //单调栈 stack<char> stk; string res; for(int i = 0; i < num.size(); i++){ //建立单调递增栈，需要把前k个不符合单调递增（大的值）去掉，
这样得出的数值小 while(!stk.empty() && stk.top() > num[i] && k > 0){ stk.pop(); k--; } stk.push(num[i]); } while(!stk.empty()){ res = stk.top() + res; stk.pop(); } res = res.substr(0, num.size() - k); //corner case: 重复的情况 int idx = 0; while(res[idx] == '0' && idx < res.size()){ //corner case: 0打头 idx++; } res = res.substr(idx); return res.size() ? res : "0"; } };