2020-06-04 402. Remove K Digits

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

My answer / NAC

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    if(num.length===k) return "0";
    var arr = num.split("");
    var minNum;
    for(var i=0; i<arr.length; i++) {
        var newNum = arr.slice(0, i).concat(arr.slice(i+1)).join``;
        if(!minNum || Number(newNum)<Number(minNum)) minNum = newNum;
    }
    return k==0 ? num : removeKdigits(minNum, k-1).replace(/^0+(?=\d+)/,"");
};

用递归的方式，能够解题，但是性能不行，会TimeOut

Best answer

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    var ptrs = Array.from(Array(num.length-k), (_,i)=>i+k);
    // ptrs[i]的数值代表的是第i个指针在num中的下标，因此取该值写法：num[ptrs[i]]
    for(let i=0; i<num.length; i++) {
        var min = i>0 ? ptrs[i-1] : -1;
        for(let j=ptrs[i]-1; j>min; j--){
            if(num[j]<=num[ptrs[i]]) ptrs[i] = j;
        }
    }
    var res = ptrs.map(t=>num[t]).join``.replace(/^0*/g,"");
    return res.length>0 ? res : "0";
};

• 采用了一个ptrs的数组来存储(num.length-k)个指针

1. Create tracking array by slicing first k chars
   Track array is a list of "pointers" to indices (not the actual chars)
   2 6 3 4 8 1
   ____ ↑ ↑ ↑ ↑
2. Start moving each "arrow" from right to left in order to find an index with value that is lower or equal to the current one
   For example:
   "arrow" pointing to "3" will move to "2" index
   2 6 3 4 8 1
   ↑ ____ ↑ ↑ ↑
   "arrow" pointing to "4" will move to "3" index (it can not move to "2", it's already taken)
   2 6 3 4 8 1
   ↑ __ ↑ _ ↑ ↑
   "arrow" pointing to "8" cannot move
   "arrow" pointing to "1" cannot move
   result: 2381
3. Map track indices to the actual chars, join array, make some zero checks

Recap

• 换种思维或许能够解决复杂的问题，比如说这个剔除数字的肯定会剔除比ptrs[i]大的留下小于等于它的num[j]