矩阵中最大矩形 Maximal Rectangle

题目：在一个M * N的矩阵中，所有的元素只有0和1， 找出只包含1的最大矩形。

例如：图中是一个４　×　６的矩形，画出红色的是我们要找到的区域。

https://blog.csdn.net/jiyanfeng1/article/details/8068676

查找最大矩形，所以它一定是以 某个行元素开始的，将要找到的某个矩形就转换成 一某一个行开始的最大矩形Histogram问题。

原始矩形可以变成如下的形式的数据：

0	1	0	1	0	0
0	2	1	0	0	1
1	3	2	0	1	0
0	0	0	0	0	1

Largest Rectangle in Histogram问题：

两个方法：

方法一：

简单的，类似于 Container With Most Water，对每个柱子，左右扩展，直到碰到比自己矮的，计算这个矩
形的面积，用一个变量记录最大的面积，复杂度 O(n^2) ，会超时。 

	public static int largestRectangleArea2(int[] heights) {
		int n = heights.length;
		int[] arr = new int[n];// 申请一个额外的数组
		arr[0] = heights[0];
		int max = heights[0]; // 最大面积

		for (int i = 1; i < n; i++) {
			arr[i] = heights[i];
			for (int j = i - 1; j >= 0; j--)
				if (arr[j] > arr[i]) {
					if (arr[j] * (i - j) > max)
						max = arr[j] * (i - j);
					arr[j] = arr[i];
				} else
					break;
			// 数组arr里的元素，保持非递减的顺序。
		}

		// 重新扫描一边，以更新最大面积
		for (int i = 0; i < n; i++)
			if (arr[i] * (n - i) > max)
				max = arr[i] * (n - i);
		return max;

	}

方法二：O(n)

如上图所示，从左到右处理直方，当 i=4 时，小于当前栈顶（即直方3），对于直方3，无论后面还是前面
的直方，都不可能得到比目前栈顶元素更高的高度了，处理掉直方3（计算从直方3到直方4之间的矩形的面
积，然后从栈里弹出）；对于直方2也是如此；直到碰到比直方4更矮的直方1。

这就意味着，可以维护一个递增的栈，每次比较栈顶与当前元素。如果当前元素大于栈顶元素，则入栈，
否则合并现有栈，直至栈顶元素小于当前元素。结尾时入栈元素0，重复合并一次。 

public static int largestRectangleArea(int[] heights) {
		Stack<Integer> s = new Stack<>();
		int result = 0;
		for (int i = 0; i <= heights.length;) {
			final int value = i < heights.length ? heights[i] : 0;
			if (s.isEmpty() || value > heights[s.peek()])
				s.push(i++);
			else {
				int tmp = s.pop();
				result = Math.max(result, heights[tmp] * (s.isEmpty() ? i : i - s.peek() - 1));
			}
		}
		return result;
	}

接下回归正题：

一行一行求解 Largest Rectangle in Histogram问题，建立滚动数组heights []

public static int maximalRectangle(int[][] matrix) {
		if (matrix.length == 0)
			return 0;
		int[] heights = new int[matrix[0].length];
		int max = 0;

		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (matrix[i][j] == 1)
					heights[j] += 1;
				else
					heights[j] = 0;
			}

			max = Math.max(max, largestRectangleArea(heights));
		}

		return max;

	}