专栏名称: 算法与数据结构
算法与数据结构知识、资源分享
目录
相关文章推荐
算法爱好者  ·  苹果设计炸了!Liquid Glass ... ·  昨天  
九章算法  ·  谷歌面试给面试官整笑了! ·  昨天  
九章算法  ·  Meta招聘软件工程师,年薪$21.3w-$ ... ·  2 天前  
九章算法  ·  Dropbox打响“反RTO”第一枪!解读北 ... ·  2 天前  
算法爱好者  ·  被微软裁员后,3 人自杀! ·  3 天前  
51好读  ›  专栏  ›  算法与数据结构

知其所以然之永不遗忘的算法

算法与数据结构  · 公众号  · 算法  · 2016-10-18 11:07

正文

请到「今天看啥」查看全文


一个好问题

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:

  1. 如果当前bar的高度大于栈顶bar的高度,则将当前bar的下标入栈;

  2. 否则执行出栈操作,记录弹出下标对应的bar的高度,并计算出一个面积,然后用这个面积更新最大面积。

代码也是相当简洁,python源码如下:

1







请到「今天看啥」查看全文