贪心算法+实例：删掉K个数后最小的数字+leetcode402

图片来自：程序员小灰（微信公众号）

 

在求解最优化问题时通常在每个步骤都要面临多种选择。对于某些情况，使用动态规划算法来求最优解十分浪费时间空间复杂度，可以使用更简单高效的贪心算法。 

贪心算法在每一步看起来都是当时最佳的选择。意思是，它总是做出局部最优的选择，希望该选择能导致全局最优。虽然贪心算法并不一定能求得最优解。 

 

贪心算法建议通过一系列的步骤来构造问题的解，每一步对目前构造的部分解 做一个扩展，直到获得问题的完整解为止。这个技术的核心是，所做的每一步都必须满足以下条件： 

 

1、可行的：它必须满足问题的约束 

2、局部最优：他是当前步骤所有可行选择中最佳的局部选择 

3、不可取消：选择一旦做出，在之后的步骤便无法更改 

 

 

例题见删除K个数字后的最小数字+leetcode402 

 

 

 

 

给定的整数大小可以超过long，所以需要使用字符串来表示。 

注意，此题不能从大数先开始删，数字大小固然重要，但是更重要的是数字的位置。否则，一味的考虑数字大小会得到如下： 

 

现在让我们把问题简化一下，若只删除一个数字，如何得到最小？ 

最重要的是数字的位置，最高位的数字哪怕至少了1，对原来数字的影响也是非常大的。 

根据此 我们可以采用如下思路： 

 

当当前数字大于右边数字的时候，删除当前数字，这样一来，补充当前数字的位置的是右边数字，自然值就变小了。 

比如： 

 

而下一个要删除的数字就是4  再下一个就是7 

 

这样得到的便是k=3时候的解。这种基于局部最优的解法最终得到全局最优我们便把他叫做贪心算法。 

 

如此一来的代码实现便是两层循环外层基于k 内层基于num.size() 这样的代码效率是很低的，因为每次重新循环一次外层，就要将内层都跑一次。 

 

其实，每次循环下一次k的时候，不需要重新循环num。不妨将num作为外层循环 将k作为内层循环。 

 

使用一个栈来维护所给数字，充分利用栈的特性。在遍历原数字时，让所有数字一个一个入栈，当某个数字需要删除时，则让他出栈。 

 

 

 

代码只对数字遍历了一遍，所以时间复杂度是o（n），空间复杂度也是o（n） 

代码如下例题： 

 

 

 

题目比较新颖，是一个典型的贪婪做法，具体思路见题目 

 

Python：