今日面试题:最大矩形

在一个位图中找面积最大的白色矩形:给你一个NxN的黑白位图,找一个面积最大的全白色的矩形。注意了,是一个矩形,不是任意一个白色相连的区域。你的算法能够达到的最好的时间复杂度是多少呢?

===================

第n杯水分析

原题

有一座金字塔,从上到下,第一层有一个杯子、第二层有两个杯子,依次类推。对杯子进行编号,有如下的形状:

1
2 3
4 5 6

每个杯子的容量为C升,从塔顶倒下L升水,当1号杯子满了之后,会等量溢出到2号和3号杯子。当2号和3号满了,2号溢出到4号和5号,3号溢出到5号和6号,注意5号接受来自两个杯子的水。依次类推。给定C和L,请问,第n杯里有多少水。

分析

这个类型的题目,关键点就是明了水倒下来的过程。我们这里做简单的分析, 假设L>C, 如果L

金字塔深度 0 1 1 2 2 2
杯号 1 2 3 4 5 6
A索引 0 1 2 3 4 5

观察上面的表格,我们会发现,一个规律,i号杯深度为h,则i号中溢出的水,将平分进入:

i + h + 1

i + h + 2

比如,文章开始的图中,3号杯进入5号和六号,3号杯的h为1,则

5 = 3 + 1 + 1

6 = 3 + 2 + 2

利用这个技巧,可以在数组中存储树形的金字塔,并且可以很方便的找到孩子节点。

计算出所有的A[i]之后,要得到最后的答案,还有一部之遥。即:

A[i] >= C ? C : A[i]

【分析完毕】

本文来自微信:待字闺中,2013-07-31发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。 【分析完毕】