任何一个位置都仅仅进出栈1次，所以时间复杂度为O (M )

如果矩阵的大小为O (N ×M )，本题可以做到时间复杂度为O (N ×M )。解法的具体过程为：

1．矩阵的行数为N ，以每一行做切割，统计以当前行作为底的情况下，每个位置往上的1的数量。使用高度数组height来表示。

例如：

map = 1 0 1 1 1 1 1 1 1 1 1 0

以第1行做切割后，height={1，0，1，1}，height[j]表示目前的底上（第1行），j 位置往上（包括j 位置）有多少连续的1。

以第2行做切割后，height={2，1，2，2}，注意到从第一行到第二行，height数组的更新是十分方便的，即height[j] = map[i][j]==0 ? 0 : height[j]+1。

以第3行做切割后，height={3，2，3，0}。

2．对于每一次切割，都利用更新后的height数组来求出以每一行为底的情况下，最大的矩形是什么。那么这么多次切割中，最大的那个矩形就是我们要的。

整个过程就是如下代码中的maxRecSize方法。步骤2的实现是如下代码中的maxRecFromBottom方法。

下面重点介绍一下步骤2如何快速地实现，这也是这道题最重要的部分，如果height数组的长度为M ，那么求解步骤2的过程可以做到时间复杂度为O (M )。

对于height数组，读者可以理解为一个直方图，比如{3，2，3，0}，其实就是如图1-6所示的直方图。

图1-6

也就是说，步骤2的实质是在一个大的直方图中求最大矩形的面积。如果我们能够求出以每一根柱子扩展出去的最大矩形，那么其中最大的矩形就是我们想找的。比如：

●　第1根高度为3的柱子向左无法扩展，它的右边是2，比3小，所以向右也无法扩展，则以第1根柱子为高度的矩形面积就是3*1==3；

●　第2根高度为2的柱子向左可以扩1个距离，因为它的左边是3，比2大；右边的柱子也是3，所以向右也可以扩1个距离，则以第2根柱子为高度的矩形面积就是2*3==6；

●　第3根高度为3的柱子向左没法扩展，向右也没法扩展，则以第3根柱子为高度的矩形面积就是3*1==3；

●　第4根高度为0的柱子向左没法扩展，向右也没法扩展，则以第4根柱子为高度的矩形面积就是0*1==0；

所以，当前直方图中最大的矩形面积就是6，也就是图1-6中虚线框住的部分。

考查每一根柱子最大能扩多大，这个行为的实质就是找到柱子左边刚比它小的柱子位置在哪里，以及右边刚比它小的柱子位置在哪里。这个过程怎么计算最快呢？用栈。

为了方便表述，我们以height={3，4，5，4，3，6}为例说明如何根据height数组求其中的最大矩形。具体过程如下：

1．生成一个栈，记为stack，从左到右遍历height数组，每遍历一个位置，都会把位置压进stack中。

2．遍历到height的0位置，height[0]=3，此时stack为空，直接将位置0压入栈中，此时stack从栈顶到栈底为{0}。

3．遍历到height的1位置，height[1]=4，此时stack的栈顶为位置0，值为height[0]=3，又有height[1]>height[0]，那么将位置1直接压入stack。这一步体现了遍历过程中的一个关键逻辑：只有当前i位置的值height[i]大于当前栈顶位置所代表的值(height[stack.peek()])，则i位置才可以压入stack。

所以可以知道，stack中从栈顶到栈底的位置所代表的值是依次递减，并且无重复值，此时stack从栈顶到栈底为{1，0}。

4．遍历到height的2位置，height[2]=5，与步骤3的情况完全一样，所以直接将位置2压入stack，此时stack从栈顶到栈底为{2，1，0}。

5．遍历到height的3位置，height[3]=4，此时stack的栈顶为位置2，值为height[2]=5，又有height[3]<height[2]。此时又出现了一个遍历过程中的关键逻辑，即如果当前i 位置的值height[i]小于或等于当前栈顶位置所代表的值(height[stack.peek()])，则把栈中存的位置不断弹出，直到某一个栈顶所代表的值小于height[i]，再把位置i 压入，并在这期间做如下处理：

1）假设当前弹出的栈顶位置记为位置j ，弹出栈顶之后，新的栈顶记为k 。然后我们开始考虑位置j 的柱子向右和向左最远能扩到哪里。

2）对位置j 的柱子来说，向右最远能扩到哪里呢？

如果height[j]>height[i]，那么i -1位置就是向右能扩到的最远位置。因为j 之所以被弹出，就是因为遇到了第一个比位置j 值小的位置。

如果height[j]==height[i]，那么i -1位置不一定是向右能扩到的最远位置，只是起码能扩到的位置。那怎么办呢？

可以肯定的是，在这种情况下，i 位置的柱子向左必然也可以扩到j 位置。也就是说，j 位置的柱子扩出来的最大矩形和i 位置的柱子扩出来的最大矩形是同一个。

所以，此时可以不再计算j 位置的柱子能扩出来的最大矩形，因为位置i 肯定要压入到栈中，那就等位置i 弹出的时候再说。

3）对位置j 的柱子来说，向左最远能扩到哪里呢？

肯定是k +1位置。首先，height[k+1..j-1]之间不可能有小于或等于height[k]的值，否则k 位置早从栈里弹出了。

然后因为在栈里k 位置和j 位置原本是相邻的，并且从栈顶到栈底的位置所代表的值是依次递减并且无重复值，所以在height[k+1..j-1]之间不可能有大于或等于height[k]，同时又小于或等于height[j]的，因为如果有这样的值，k 和j 在栈中就不可能相邻。

所以，height[k+1..j-1]之间的值必然是既大于height[k]，又大于height[j]的，所以j 位置的柱子向左最远可以扩到k +1位置。

4）综上所述，j 位置的柱子能扩出来的最大矩形为(i-k-1)*height[j]。

以例子来说明：

① i==3，height[3]=4，此时stack的栈顶为位置2，值为height[2]=5，故height[3]<=height[2]，所以位置2被弹出（j==2），当前栈顶变为1（k==1）。位置2的柱子扩出来的最大矩形面积为(3-1-1)*5==5。

② i==3，height[3]=4，此时stack的栈顶为位置1，值为height[1]=4，故height[3]<=height[1]，所以位置1被弹出（j==1），当前栈顶变为1（k==0）。位置1的柱子扩出来的最大矩形面积为(3-0-1)*4==8，这个值实际上是不对的（偏小），但在位置3被弹出的时候是能够重新正确计算得到的。

③ i==3，height[3]=4，此时stack的栈顶为位置0，值为height[0]=3，这时height[3]<=height[2]，所以位置0不弹出。

④将位置3压入stack，stack从栈顶到栈底为{3，0}。

6．遍历到height的4位置，height[4]=3。与步骤5的情况类似，以下是弹出过程：

1）i==4，height[4]=3，此时stack的栈顶为位置3，值为height[3]=4，故height[4]<=height[3]，所以位置3被弹出（j==3），当前栈顶变为0（k==0）。位置3的柱子扩出来的最大矩形面积为(4-0-1)*4==12。这个最大面积也是位置1的柱子扩出来的最大矩形面积，在位置1被弹出时，这个矩形其实没有找到，但在位置3这里找到了。

2）i==4，height[4]=3，此时stack的栈顶为位置0，值为height[0]=3，故height[4]<=height[0]，所以位置0被弹出（j==0），当前没有了栈顶元素，此时可以认为k==-1。位置0的柱子扩出来的最大矩形面积为(4-(-1)-1)*3==12，这个值实际上是不对的（偏小），但在位置4被弹出时是能够重新正确计算得到的。

3）栈已经为空，所以将位置4压入stack，此时从栈顶到栈底为{4}。

7．遍历到height的5位置，height[5]=6，情况和步骤3类似，直接压入位置5，此时从栈顶到栈底为{5，4}。

8．遍历结束后，stack中仍有位置没有经历扩的过程，从栈顶到栈底为{5，4}。此时因为height数组再往右不能扩出去，所以认为i==height.length==6且越界之后的值极小，然后开始弹出留在栈中的位置：

1）i==6，height[6]极小，此时stack的栈顶为位置5，值为height[5]=6，故height[6]<=height[5]，所以位置6被弹出（j==6），当前栈顶变为4（k==4）。位置5的柱子扩出来的最大矩形面积为(6-4-1)*6==6。

2）i==6，height[6]极小，此时stack的栈顶为位置4，值为height[4]=3，故height[6]<=height[4]，所以位置4被弹出（j==4），栈空了，此时可以认为k==-1。位置4的柱子扩出来的最大矩形面积为(6-(-1)-1)*3==18。这个最大面积也是位置0的柱子扩出来的最大矩形面积，在位置0被弹出的时候，这个矩形其实没有找到，但在位置4这里找到了。

3）栈已经空了，过程结束。

9．整个过程结束，所有找到的最大矩形面积中18是最大的，所以返回18。

研究以上9个步骤时我们发现，任何一个位置都仅仅进出栈1次，所以时间复杂度为O (M )。既然每做一次切割处理的时间复杂度为O (M )，一共做N 次，则总的时间复杂度为O (N ×M )。

全部过程参看如下代码中的maxRecSize方法。9个步骤的详细过程参看代码中的maxRecFromBottom方法。

public int maxRecSize(int[][] map) { if (map == null || map.length == 0 || map[0].length == 0) { return 0; } int maxArea = 0; int[] height = new int[map[0].length]; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { height[j] = map[i][j] == 0 ? 0 : height[j] + 1; } maxArea = Math.max(maxRecFromBottom(height), maxArea); } return maxArea; } public int maxRecFromBottom(int[] height) { if (height == null || height.length == 0) { return 0; } int maxArea = 0; Stackstack = new Stack(); for (int i = 0; i < height.length; i++) { while (! stack.isEmpty() && height[i] <= height[stack.peek()]) { int j = stack.pop(); int k = stack.isEmpty() ? -1 : stack.peek(); int curArea = (i - k - 1) * height[j]; maxArea = Math.max(maxArea, curArea); } stack.push(i); } while (! stack.isEmpty()) { int j = stack.pop(); int k = stack.isEmpty() ? -1 : stack.peek(); int curArea = (height.length - k - 1) * height[j]; maxArea = Math.max(maxArea, curArea); } return maxArea; }