上一篇博客喷了现在很多公司面试的题目，现在来复习一下稍微高级一点的算法，这些题目都是老夫曾经做过的，拿出来“温故而【不】知新”。
弱智版放鱼缸
问题描述：
刀之魂最近准备在公司放一个“小”鱼缸，市场上买的鱼缸都不够大，于是刀之魂找了一家厂商定制。但是生产鱼缸的厂家很脑残，只能做出底面为正方形的。
众所周知，公司有很多工位和其他物品，所以能放置这个鱼缸的区域有限。但是由于刀之魂想尽可能地霸占公司已有的空地，因此想找到一块面积最大的地方来放置鱼缸。再次注意，鱼缸的底面是正方形的。
现在请乃帮刀之魂找一块面积最大的正方形空地，以便刀之魂找厂家定制合适大小的鱼缸。
输入：
输入的内容是一个二维数组（int[][]），其中每一个元素都为 0 或 1。其中 0 表示空地，1 表示位置被占用而不能放置鱼缸。
输出：
一个整数，表示可放置鱼缸的最大正方形的边长。
示例：
1 1 0 0 1 1 1
1 0 0 0 1 1 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
输出为：3 （红色部分标明的正方形边长）。
问题来源：
刀之魂根据经典问题改编（超级弱智题）。
问题分析：暴力搜索的复杂度为 O(mn^2) （若 n < m）。采用暴力搜索时，对于每一个位置 (i, j)，假设此位置为正方形的右下角，那么第一次需要判断 (i-1, j)、(i, j-1) 以及 (i-1,j-1) 三个坐标是否全为空，如果是，则边长成功扩展成 2。接下来需要再判断是否扩展成 3，此时需要再判断 (i-2, j-2)、(i-1,j-2)、(i, j-2)、(i-2, j)、(i-1,j) 是否全为 0，依次类推。
但是我们发现，在判断 (i-1, j-1) 时已经对以前的区域进行过判断，再去判断是多余的。所以可以把以前的判断结果记录下来，这样就可以用到动态规划了。
令 f(i, j) 表示以 (i, j) 为右下角时，正方形的最大边长。
见上图，当我们处理到红色方框的右下角 (i, j) 时，可以用到 f(i-1, j-1) 的值（紫色框的区域，记为 M），正方形的边长可以加 1 当前仅当：（1） f(i, j) = 0；（2） f(i-1 .. i-M, j-1 .. j-M) 都为 0。
对于条件（2），我们可以利用 f(i-1, j) 以及 f(i, j-1) 的值进行判断，如果这两个位置的边长大于 M，那么条件（2）一定成立，见上图绿色和蓝色方框没有重叠的部分。
假如条件（2）不成立，那么新的正方形边框最多为多少呢？因为 f(i-1, j-1) 限制了正方形最大可以扩展的边长，因此正方形的左方和上方必然不能超过这个区域。如果 f(i-1, j) 和 f(i, j-1) 有一个小于 M，说明该点的上方或者左方有为 1 的位置，此时正方形顶多只能扩展到 f(i-1, j) 和 f(i, j-1) 中较小的一个（乃可以自己画图模拟一下）。因此，我们就有以下的条件转移方程：
所以算法的时间复杂度为 O(mn)。注意到当前行仅与前一行有关，可以反复使用同两个一维数组（其实上一行与当前行重叠的 j 只有一个，因此可以用一个一维数组+临时变量），所以空间可以优化到 O(m)。
加强版放鱼缸
问题描述：现在鱼缸生产厂家改进了工艺，可以生产底面为矩形的鱼缸了。现在求公司能放置鱼缸的最大矩形区域的面积。
问题分析：由于是矩形，上述“简单的”转移方程就不适用了，我们又要想新法子。这个题其实是比较难的，貌似没有啥头绪，我们不妨看一下 LeetCode 上的一个简化版的题目（LeetCode 第 84 题）。
简化版查找最大矩形
问题描述：给你一个柱状图，每一个柱子的宽度都为 1，如下图所示。找出这个柱状图中的最大矩形的面积。
问题分析：一看这道题就知道必须要用 O(n) 的算法出解，因为暴力搜索也仅仅是 O(n^2) 的复杂度。我们可以考虑分治，这样复杂度可以降到 O(nlog n)，不过这个柱状图的规则实在是太简单，肯定还有更好的办法。
我们从左至右遍历每一个柱子，当遍历到第 i 个时，我们假设柱子 i 就是面积最大的矩形里高度【最小】的柱子。这样，当所有柱子遍历完时，由于每一个柱子都考虑过了，因此一定能找到最大值。
对于柱子 i，我们需要找到它左右两侧高度小于它的【第一根】柱子，这样，最大矩形的面积就是在左右两侧高度比它小的柱子之间（再次强调我们假设第 i 根柱子在最大面积的矩形中高度最矮）。此时面积就是这根柱子的高度 × 两侧的宽度。那么怎么在 O(1) 时间内找到这个范围呢？
此时想到以前做过的一个题目：写一个栈，要求 push 和 pop 操作都为 O(1)，并且要随时能访问栈内最小元素的值。解决方法是设置一个 minStack，当入栈元素比栈顶元素小或者相等时，minStack 同时入栈；如果比栈顶大，不需要操作 minStack。（当然此题有一种天才解法不需要设置 minStack，O(1) 的空间即可解决。请自行参考其他资料。）
这里我们也可以设置一个栈，进行如下操作：
- 如果柱子 i 比栈顶元素高或者相等（或者栈为空），则柱子 i 的入栈。
- 如果柱子 i 比栈顶元素小，则从栈中取出元素，一直到栈顶元素比柱子 i 矮。
对于每一个出栈的柱子 k，高度比 i 小，我们假设柱子 k 是所求矩形中高度最矮的（即最开始分析的柱子 i ），现在要在 O(1) 的时间找左右边界，问题就很简单了。
由于我们的栈一直是高度比栈顶高的才入栈（对于相等的情况，下一个元素将会进行判断！），所以 k 在栈内的前一个元素高度一定比它小，所以它就是左边界！而我们遍历到的柱子 i，由于比 k 矮，所以 i 就是右边界！所以以 k 为最小高度的矩形面积就为 height[k] * (i – height[stack.top()] – 1)。如果栈空了怎么办呢？说明左边的柱子都比它高，取 i 作为宽度即可。
当我们遍历完最后一根柱子后，栈可能还没空。把它们挨个取出来，重复上面的步骤即可。
总的时间复杂度为 O(n)。
继续：加强版鱼缸
做了上面那道题后，我们很容易想到这个题也能用类似的方法做！遍历矩阵的每一行，假设这一行就是“底部”，然后按照上面的方法即可。不过不同之处在于，这里给出的是一个矩阵，因此每个“柱子”的高度还需要自己计算。这个不难，我们搞一个 height[] 数组，遍历每一行第 i 个位置时如果能放鱼缸则 height[i]++，否则 height[i] 清零即可。
但是天才的 morrischen2008 想到了一个更好的办法。
还是像上面那样遍历，用 height[] 数组记录以此为底的柱子的高度。另外，这哥们另外使用了两个数组 left[] 和 right[]。分别记录以 height[j] 为高度时，矩形的左右边距。
这哥们给了一个例子，假如矩阵为（这道题用 1 表示“空闲区域”，因此与“鱼缸”问题相反）：
0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0
对于第三行（i = 2），height 数组为 {0, 1, 2, 3, 2, 1, 0}。
而 left 数组为 {0, 1, 2, 3, 2, 1, 0}。以 j = 2 为例（红色标识的数字），以 height[2] = 2 为高度的矩形左侧坐标即为 2。具体可以用以下代码遍历出：
for(int j=0; j<n; j++) { // compute left (from left to right)
if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
注意在计算 left[j] 时，max函数中的 left[j] 表示【上一行】的计算的 i = 1, j = 2 的值，因为对于上一行来说，left[j] 表示 height[j] – 1 时的左边距，本行所求得的矩形左边距【不可能】比上一行还靠左（不然就不是矩形了）。如果本行的左边距（cur_left）比上一行的要靠右，那就得取本行的左边距了。总之取靠右的那个。
在计算 right 数组时，j = 2 时数组为 {7, 6, 5, 4, 5, 6, 7}，同理表示以 height[j] 为高度时矩形的右边距，因此代码是：
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n; cur_right=j;}
此时，对于第 j 列，最大矩形的面积就是：(right[j] – left[j]) * height[j]。
实在佩服想出这个办法的哥们。
大招：青蛙过河问题
这是老夫相当喜欢的一个题目，至于题目来源先不说，以免打击到乃。在面试时，老夫每次都想出这个问题，但是考虑到基本上没有人能完全正确地做出，所以一直没问过。这个问题是这样的：
问题描述：有一个长度为 L 的桥，青蛙想从桥的一端跳到另外一端。青蛙初始时在坐标为 0 的位置，每次能够向前跳 [M, N] 的长度（只能为整数）。当青蛙跳到 L – 1 的位置或者更后，就视为青蛙已经过河了。
桥上的某些位置有非常可恶的小石子，青蛙想尽可能少地踩到石子上。青蛙要过河，最少要踩到几次石子。
输入格式：
L M N K
K 个数以空格隔开，表示各石子的坐标。
问题分析：老夫做这个题的时候，一看，这个简单，就是个走迷宫问题的升级版，所以顺手可以写出转移方程。令 f(n) 表示青蛙跳到 n 位置时，最少要踩的石子数，d(i) = 0 表示当前位置没有石子，d(i) = 1 表示当前位置有石子。那么：
f(n) = min{f(n-k)} + d(i) M<=k<=N
Done！
不过别高兴得太早，老夫还没说题目中各值的取值范围，我们有：
数据范围：L <= 10^9，1<=M<=N<=10，0<K<=100。要求一秒出解。
继续分析：一看这个数据范围顿时傻眼了，L 最多为 10^9，即使是 O(n) 的算法也不可能在一秒内出解！
这是老夫【高中】时参加“信息学联赛”时的一道题目。乃不妨想想看乃现在能不能做出来这道高中生的题目。
———————————————————
————ＴＨＩＮＫＩＮＧ．．．————
———————————————————
这道题一共有 10 组测试数据。如果乃直接用上面的递推方法，恭喜你，你最多能过 3 组数据，其他数据全部会超时。
我们仔细分析一下数据范围，石子最多只有 100 个，这意味着什么？桥上一定有大片区域是空白！然后，青蛙每次最多只能跳 10 步，而对于某个大间距的空白……
提示到这里估计乃已经想到了，就是这么大段空白完全没用，可以直接跳过去！
由于 M 和 N 都不超过 10，乃可以随便找两个数字模拟一下，会发现，在位置超过 (M-1)×(N-1) 的位置后，所有位置一定可以跳到！（这个凭想象也能猜到。在数学上，有一个“裴蜀定理”，ax + by = m，当且仅当 m 是 a 和 b 的最大公约数的整数倍时，方程有无穷多个解。）
因此，如果空白超过一定长度，就可以丢掉。本题中取 100 以上就好了（具体可以用 M 和 N 算出来，这个乃自己算吧），超过 100 的空白区域压缩成 100 再进行递推，这样复杂度就大大降低了，很轻松在一秒内出解。
另外我们注意到，如果 M=N，那么状态无论如何都不能被压缩！此时我们只需要对每一个石子的位置求余就可以算出要踩多少个石子了（M=N 的数据有一组，如果乃忘了这种情况，就要丢 10 分）。
比如乃可以写出下面酱紫的代码来压缩状态：
for (int i=1;i<=m;i++){
int tmp=min(stone[i]-stone[i-1],100);
l+=tmp,a[l]=1;
}
乃把代码写好后欣喜若狂。等成绩公布后乃发现如此深思熟虑考虑了状态压缩以及 M=N 的情况后，特么的居然只得了 60 分。还有 40 分跑哪去了！
———————————————————
————ＴＨＩＮＫＩＮＧ．．．————
———————————————————
所以这个题目还有一个超级大坑（当时老夫就是掉到坑里去了！）：
输入的 K 个石子的坐标没说是有序的！所以要先排序！！！