###最大矩形
####原题 在一个位图中找面积最大的白色矩形：给你一个NxN的黑白位图，找一个面积最大的全白色的矩形。注意了，是一个矩形，不是任意一个白色相连的区域。你的算法能够达到的最好的时间复杂度是多少呢？
####分析 为了方便进行分析，我们假设黑色位置都是0，白色的位置都是1.题目的问题就转化为，找到一个最大的矩形，其中所有的元素都是1.
遇到这样的题目，该如何分析呢？这是一个矩形，是二维，是否是由一维的某些问题扩展而来的呢？一维的问题的解法，是否可以扩展到二维呢？我们看下面的题目：
在柱状图中找最大的矩形：给一组非负的整数来表示一个柱状图，设计一个算法找到最大面积的能适合到柱状图内的矩形。比如，对与这组数，1 2 3 4 1 ，有两种可能的方案，一种是适合到 2 3 4 内的矩形，面积是 23；另一种是适合到 3 4 内的矩形，面积是 32。你觉得能有O(n)算法吗？
上面的题目，我们在微博上都讨论过的。大家还记得，一维的时候，是怎么样的解法么？思路如下：
一个线性算法是用堆栈来保存当前可能的矩形（高度和起始位置）。从左到右扫描，对一个元素，如果 a）大于栈顶元素， push； b）小于的话，pop所有的大于它的元素，计算面积，更新最大值。这时如果堆栈空，push一个新的元素，高度等于当前元素，起始位置为0；否则，push当前元素高度和栈顶的起始位置。
这是一个很巧妙的解法，是否能够应用到二维的情况呢？在微博中，我们简短的给出了一个思路。下面，我们在这里详细讨论，针对如下例子，有矩阵A：
| 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
上面的这个矩阵，该如何转化为一维的情况处理呢？最直接的思路如下：
- 第一行作为一维的情况处理；
- 第一行、第二行，对应列相加，生成一个新的数组，然后应用一维的处理情况；
- 第一行、第二行、第三行，对应列相加，生成一个新的数组，然后应用一维的处理情况；
- ...直到整个矩阵都包括在内；
- 第二行作为一维的情况处理；
- 第二行、第三行，对应列相加，生成一个新的数组，然后应用一维的处理情况；
- ...一次类推
上面的思路是可行的，但是时间复杂度是n^3的。如何进一步改进呢？思路也是从上面的过程中得到的。
生成新的矩阵C,C[i][j]表示第j列，从第i个元素开始，包括第i个元素，向上数，直到遇到0时，1的个数。则C为：
| 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 2 | 1 | 1 | 2 | 1 |
| 1 | 3 | 2 | 2 | 3 | 0 |
| 0 | 0 | 3 | 3 | 0 | 0 |
上面这个矩阵的构造，遍历一边A的全部元素即可。n^2的时间复杂度。这个矩阵的最大作用，就是将上面思路中，跨几行考虑的情况，都变为一行了。时间复杂度降了一个级别，每一行，应用一维处理处理的情况，就可以得到最终的结果。
将上面斜体的描述转换为如下步骤：(h, i)，h表示C[i][j]的大小，可以理解为矩形的高度，i表示起始位置，第三行为例：
| i | C[i] | 栈操作 | 最大值 | 栈内容 |
| 0 | 1 | push (1,0) | (1,0) | |
| 1 | 3 | push (3,1) | (3,1)(1,0) | |
| 2 | 2 | pop (3,1),push (2,1) | (2-1)*3=3 | (2,1)(1,0) |
| 3 | 2 | 什么都不做 | (2,1)(1,0) | |
| 4 | 3 | push(3,4) | (3,4)(2,1)(1,0) | |
| 5 | 0 | pop(3,4) | (5-4)*3=3 | (2,1)(1,0) |
| 5 | 0 | pop(2,1) | (5-1)*2=8 | (1,0) |
| 5 | 0 | pop(1,0) | (5-0)*1=5 |
则得到这一行的最大值为8。
总结算法过程如下：
- 初始(h,0)，入栈；
- 遍历后续元素：
-
- 如果h > h_top, 则入栈；
-
- 如果h = h_top, 则不进行任何操作；
-
- 如果h < h_top, 出栈，直到栈顶元素的高度小于h，每次出栈，更新最大值(i - i_pop)*h_pop > max ? (i - i_pop)*h_pop : max；此时如果h>h_top,则push (h, i_lastpop)，如果栈为空，则push (h, 0).
- 直到元素遍历完毕
【分析完毕】