相信大部分同学曾经都学习过快速排序、Huffman、KMP、Dijkstra等经典算法，初次学习时我们惊叹于算法的巧妙，同时被设计者的智慧所折服。于是，我们仔细研读算法的每一步，甚至去证明算法的正确性，或者是去尝试优雅地实现这些算法。总之，我们会花费很大的时间精力去理解这些智慧的结晶。 然而，现在对于这些经典的算法你仍然了然于胸吗？就算现在你仍然记得这些算法的步骤，你敢确保一年后、十年后自己不会忘记？我想没有多少人敢保证吧。 我们当然希望自己掌握一个算法后，就永远不会忘记，最好还能举一反三，利用算法中的思想去解决新的问题。然而，现实与美好的愿景往往是背道而驰，不要说举一反三，我们甚至经常忘记那些算法本身。 背算法与设计算法 为什么会这样？简单来说，因为我们从来就没有真正掌握过这些算法，我们只不过是在背诵别人发明的算法，就像我们背诵历史书上的那些历史事件一样，时间久了自然会慢慢遗忘。 我们接触到某个算法时，看到的只是对算法过程的讲解，对其正确性的证明，或者对其效率的分析（想想大名鼎鼎的《算法导论》，《算法》是如何讲解某一算法的），我们不会看到那些牛人是如何“灵机一动”设计出了这惊天地泣鬼神的算法。也就是说我们只是知其然，并没有知其所以然。当我们不知道一个算法的来龙去脉，不知道设计它经历的那些思维历程时，就很容易忘记它的具体内容。相反，那些牛人就不会忘记自己设计的算法。 所以，当看到别人牛逼的闪闪发光的算法后，我们一定要探寻算法背后那“曲径通幽”的思维之路。只有经历了思维之路的磨难，才配得上永远占有一个算法，并有可能举一反三，或者是设计一个巧妙算法。刘未鹏在知其所以然（三）：为什么算法这么难？中探索了Huffman编码的思维历程，值得一看。顺便说一下，探索算法背后的思维历程不是件容易的事，要知道就是霍夫曼本人也是花了一个学期才想出它的编码算法。 下面我们以LeetCode上一个好问题，来探索这个问题的算法背后的思维之路。关于什么是好问题，刘未鹏在跟波利亚学解题上有一个不错的观点：好问题即测试一个人思维的习惯的题目，通常考察你的联想能力、类比能力、抽象能力、演绎能力、归纳能力、观察能力、发散能力等。 一个好问题 LeetCode 84题：Largest Rectangle in Histogram，给定一个直方图（下图a），求直方图中能够组成的所有矩形中，面积最大为多少。对于图a来说，我们很容易看出来面积最大的矩形为高度为5和6的直方图组成的矩形（图b隐形部分），其面积为5 * 2 = 10。 其实这个题稍微加以变化，就是另一个相当有趣的问题：Maximal Rectangle。 这道题目一个显而易见的解决方法就是暴力搜索：找出所有可能的矩形，然后求出面积最大的那个。要找出所有可能的矩形，只需要从左到右扫描每个立柱，然后以这个立柱为矩形的左边界（假设为第i个），再向右扫面，分别以（i 1, i 2, n）为右边界确定矩形的形状。 这符合我们本能的思考过程：要找出最大的一个，就先列出所有的可能，比较大小后求出最大的那个。然而不幸的是，本能的思考过程通常是简单粗暴而又低效的，就这个题目来说，时间复杂度为N^2 。那么有没有一种更加高效的解决办法呢？ 一个好算法 我第一次面对这个题时，并没有想出一个漂亮的解决方案。因为从给定的条件来看，似乎找不到一个约束条件使得满足这个条件的矩形面积最大，也就是说无法缩减问题的规模，因此必须找出所有可能的矩形，这样的话效率肯定是N^2 。 然而去Google了一下，立即发现了一个时间复杂度O(n)的算法，当时就被这神奇的解法所震撼到。它的代码十分简单，简单到一开始我根本就看不懂，不明白为什么这样子求出的就是最大的矩形。网上好多所谓的解题报告里面只是人云亦云地给出了算法的步骤，没有算法正确性的证明，更没有我们最想要的关于解题思路。 我也先给出算法步骤和代码，看看你是不是同样一头雾水。在程序中维护一个栈，栈中元素为直方图中bar的下标，然后从头开始扫描每个bar：
代码也是相当简洁，python源码如下：
|
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
