Remove K Digits

 [題目]

https://leetcode.com/problems/remove-k-digits/

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

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.

給你一個數字1432219, 允許你刪掉其中3數字，例如刪掉1432219就會變成2219，刪掉1432219就會變成1321。

請問怎麼刪會使結果最小 ? 回傳最小的那個數字

[Solution]

Make most significant digit lower.

We should do our best, use all our barging chip 'k' to make most significant digit lower.

It is better than make other digit lower.

e.g.

original number = 4999

Make 4999 --> 3999 is way better than make 4999->4000. No matter how hard you try to reduce other digits, it will never be better than reduce most significant digit.

Use a stack with N-K size to store the answer. Bottom is most sign digit. Top is less sign digit.

1.Since original size of number is N, and we can remove K digits from it. The best choice is to remove exactly K digits. It makes the answer lower.

2.Use a stack to put answer. Stack bottom represent the most sign digit. Stack top represent the less sign digit.

Decide digit[0]~digit[i] should stay or not according to digit[i+1].

New we are pushing digit into stack. 

1.When push d[0] to stack, we don't know if d[0] is a good choice for most sign digit or not. But let's assume it is (we don't have choice actually, we can't just remove d[0] without more information). So we just push d[0] into stack, and wait for more info.

2.When push d[1] to stack, there is two condition : 

   a. d[0] <= d[1]  : d[0] is lower, so d[0] is better than d[1] to be a most sign digit. Then we just simply push(d[1]).

   b. d[0] > d[1] : d[1] is lower than d[0], which makes it a better choice for that slot, so we let d[1] take d[0]'s place. 

       We pop d[0] and push d[1], so d[1] replace d[0] and become bottom of stack, and most sign digit.

2.b is the most important step. The core concept is : "We should not allow the big number take the most sign place. So if d[i+1] is smaller(better) than d[i](which is at stack.top()), we should pop d[i] out. Furthermore, we should pop stack continuously until stack.top() is smaller or equal to d[i+1]. "

[code] 

class Solution {
public:
    string removeKdigits(string num, int k) {
        string maxS;

        //this is doing "1/2.a/2.b" steps
        for (auto ch : num){
            while(!maxS.empty() && maxS.back() > ch && k > 0){
                maxS.pop_back();
                k--;
            }
            maxS.push_back(ch);
        }
        //if still barging chip K left, then we start pop from back(the most biggest number)
        while (k-->0) maxS.pop_back();

        //this is just to remove the 0 on the stack.bottom
        bool foundFirstNonZero=false;
        string ans;
        for (auto ch : maxS){
            if(ch!='0') foundFirstNonZero=true;
            if(foundFirstNonZero){
                ans +=ch;
            }
        }
        return ans.empty() ? "0" : ans;
    }
};