单调栈——（直方图内最大矩形 || 最大全1子矩阵 ）
单调栈
顾名思义就是说栈内的元素，按照某种方式排序下，必须是单调的。如果新入栈的元素破坏了单调性，就弹出栈内元素，直到满足单调性。
它可以很方便地求出某个数的左边或者右边第一个比它大或者小的元素，而且总时间复杂度O(N)。
直方图内最大矩阵题目地址
7表示柱形图有7个数据，分别是 2 1 4 5 1 3 3， 对应的柱形图如下，最后求出来的面积最大的图如右图所示。
分析：
要想找到里面的最大的面积，一定会有这么一种情况，得出的矩形的高度一定为所包含的某一个高度一致的。所以我们可以对某一个柱子的高度为标准，尽量的向两头扩展，这样就可以找出以它高度为标准的，并包含它本身的最大矩形。然后对每一个柱子都做类似的工作，最后挑出里面最大的矩形。
OK，单从上述所说，一定会有重复的工作，如何剔除重复工作呢？而且什么叫做尽量向两头扩展呢？
重复工作之后再说。先说什么叫尽量向两头扩展。
如：2 1 4
第一个：2，以2为高度为准，向左右两头扩展，它只能向右扩展，因为1比2低了，就不可能扩展到1了。宽度只有1。
第二个：1，以1为高度为准，向左右两头扩展，向左，因为2比1高可以扩展过去；向右，因为4也高于1所以扩展到4，这样以1为高度的矩形宽为3了；
第三个：4，以4为高度为准，向左右两头扩展，向左，因为4比1、2都高，显然不可以扩展过去，这样以4为高度的矩形宽为1了。
所以要将其扩展过去，必须高度不低于当前扩展点的高度。
所以如果我们从第一个开始计算到第n个，计算到 i 时，如果我们可以快速的找出左边第一个（这里第一的意思是离i最近）比 i 的高度小的，就可以完成了向左扩展的工作，而向右扩展，我们本来就是一直向右走，所以直接扩展。这时候就轮到：单调栈出场了！
一直保持单调递增的栈。
思考刚才的例子：
2进栈，左边无比其小的元素，记录其最左扩展位置为1
1准备进栈，因为其进栈就破坏了单调栈的性质（2>1），这时2要出栈，因为1<2也说明了2不可能向右扩展，出栈，计算以2为准的矩形 2*1，然后1才进栈。1进栈前，发现其前一个元素，既是当前的栈顶2，比1高，而且2的左扩展从位置1开始，所以1也有理由从2的左起始位置开始（注意：2比1高），所以2出栈后，1进栈，其左扩展应为2的左扩展位置1；
4准备进栈，因为4>1直接进栈，其左扩展位置只能为3了。
最后要清空栈：4退栈，以为是最右的了，这此时右扩展只能为3了。左右扩展都为3，即是其本身，矩形为4*1；记录其位置以备后需；
1退栈，最右扩展只能是上一个退栈的元素位置，因为其高度比1高（单调栈的性质），所以利用刚才记录的位置，1的左右扩展就为1，3了，矩形1*3；
具体操作：
建立一个单调递增栈，所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。
如何压栈并更新呢？
① 如果当前元素比栈顶元素大或者栈为空，则直接压栈；
② 如果当前元素小于等于栈顶元素，则退栈，直到当前元素大于栈顶元素或者栈为空时，压栈；
③ 在退栈的过程中要进行最大面积和累积宽度的更新；
注意，出栈入栈的不是是当前元素，而是在原数组中的位置。
退栈时，计算以当前退栈的元素为中心向左右两边扩展的面积。curIndex表示当前出栈元素在原数组中的索引，left表示可以扩展到最左的边界（不包括left），i表示向右扩展到第i个元素时的边界（不包括i），所有总共可以扩展的宽度即（i-left-1），再乘以当前元素，即为面积。最后更新维护最大值。
注意：当遍历完所有元素，即所有元素都入过栈，且当前栈不为空，此时，唯一不同的就是最右扩展边界从原来的i变为定值n（元素的总个数）。
package test;
import java.util.Scanner;
import java.util.Stack;
/**
* @author xiaohao
* @date 创建时间：Aug 17, 2017 11:32:13 AM
* @version 1.0
*/
public class MaxInnerRec {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
System.out.println(maxInnerRec(arr,n));
}
public static int maxInnerRec(int[] arr, int n) {
// TODO Auto-generated method stub
if(n==0)
return 0;
int max=0;
Stack <Integer>stk = new Stack <Integer>();
for(int i=0;i<n;i++)
{
while(!stk.isEmpty() && arr[stk.peek()]>=arr[i])
{
int curIndex=stk.pop();
int left=stk.isEmpty()?-1:stk.peek();
int curArea = (i-left-1)*arr[curIndex];
max=Math.max(max, curArea);
}
stk.push(i);
}
while(!stk.isEmpty())
{
int curIndex=stk.pop();
int left=stk.isEmpty()?-1:stk.peek();
int curArea=(n-left-1)*arr[curIndex];
max=Math.max(max, curArea);
}
return max;
}
}最大全1矩阵 poj3494
题目描述：
在一个M * N的矩阵中，所有的元素只有0和1，从这个矩阵中找出一个面积最大的全1子矩阵，所谓最大是指元素1的个数最多。
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是两个整数m、n(1<=m、n<=1000)：代表将要输入的矩阵的大小。
矩阵共有m行，每行有n个整数，分别是0或1，相邻两数之间严格用一个空格隔开。
- 输出：
-
对应每个测试案例，输出矩阵中面积最大的全1子矩阵的元素个数。
- 样例输入：
-
2 2 0 0 0 0 4 4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
- 样例输出：
-
0 4
可以将上述问题转化为求直方图中最大的矩形的面积，将原矩阵中的每一行视为一个直方图，对于每一行中的每一列的值，为从该行（包括此行）往上的连续1的个数，下面分别利用直方图的算法来求解每一行中的最大值，然后求出全局最大值。例如4*4的map矩阵：
1 0 1 1
1 1 1 1
1 1 1 0
0 1 0 1
原矩阵可以转化为如下矩阵，而height数组依次取矩阵的每一行，然后计算。
1 0 1 1
2 1 2 2
3 2 3 0
0 3 0 1
关键代码：
public static 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++) {//求第i行的直方图矩阵
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
}
maxArea = Math.max(maxInnerRec(height,height.length), maxArea);
}
return maxArea;
}参考
http://blog.csdn.net/qq1169091731/article/details/52006440