题目：给出一个整数，从该整数中去掉 k 个数字，要求剩下的新整数尽可能的小

例子：

1593212 删去 3 个数字 新整数的最小情况是 1212

30200 删除1个数字 新整数的最小情况是 200

10 删去2个数字 新整数最小情况是 0

思路：

例如，给出一个 整数 541 270 936 要求删去一个数字，让剩下的整数尽可能小

那么无论删除哪个数字，最后的结果都是从 9 位整数变成 8 位整数，则，同样是八位整数，显然应该优先把高位数字降低，这样对新整数的影响最大

即：把原整数的所有数字，从左到右进行比较，如果发现某一位数字大于它右侧的数字，则删除该数字后，会使该数位的值降低

像这样依次求得局部最优解，最终得到全局最优解的思想，叫做贪心算法

实现代码

1    function deleteAfterMinNumV1(num:string, k:number) {
2        let numStr = num;
3        for (let index = 0; index < k; index++) {
4            let hasCut = false
5            for (let j = 0; j < numStr.length - 1; j++) {
6                if(numStr[j] > numStr[j+1]) {
7                    numStr = numStr.slice(0, j) + numStr.slice(j+1);
8                    hasCut = true;
9                    break;
10                }
11            }
12            // 没有找到要删除的数字，就删除最后一个
13            if(!hasCut) {
14                numStr = numStr.slice(0, numStr.length - 1)
15            }
16        }
17        // 删除开头的 0 
18        while(numStr[0] === '0') {
19            numStr = numStr.slice(1, numStr.length)
20        }
21        if(numStr.length === 0) {
22            return '0'
23        }
24        return numStr
25    }
26

此算法时间复杂度为 O(kn)

此外存在一个问题：内循环每次遍历都从头开始遍历，优化方法为从上次删除的位置开始遍历

优化版本

1  function deleteAfterMinNumV2(num:string, k:number) {
2      // 创建一个栈  用于接收所有数据
3      let stack = [];
4      let deleteNum = k
5      let newNumLength = num.length - k
6      for (let index = 0; index < num.length; index++) {
7          // 当当前数组小于栈顶数字是  栈顶出栈  当前数字入栈
8          while(stack.length &amp;&amp; stack[stack.length -1] > num[index] &amp;&amp; deleteNum > 0) {
9              stack.pop()
10              deleteNum --
11          }
12          stack.push(num[index])
13      }
14      // 这里是没有找到删除的数字 把最后的删除
15      if(stack.length > newNumLength) {
16          stack = stack.slice(0, newNumLength)
17      }
18      // 除去开头的0
19      while(stack[0] === '0') {
20          stack.shift()
21      }
22      if(stack.length === 0) {
23          return '0'
24      }
25      return stack.join('')
26  }
27

利用栈的回溯性，只对原数字遍历了一次，时间复杂度为 O(n)，

利用栈来储存数字和删除数字，空间复杂度为 O(n)

摘要总结自: 漫画算法 小灰的算法之旅