地址：https://oj.leetcode.com/problems/maximal-rectangle/

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

首先吐槽下这个题目，不知道是我英语理解还是题目本身存在让人误解地方，我理解题意是最大的矩形包括所有1元素，按着这个理解我很开心的写了如下代码：代码思路很简单，类似杨氏矩阵中用到的思想：http://blog.csdn.net/huruzun/article/details/28420545

public class Solution {
        private char[][] matrix ;
	public int maximalRectangle(char[][] matrix) {
		if(matrix.length == 0){
			return 0;
		}
		int row = matrix.length;
		int col = matrix[0].length;
		int ans = 0;
		this.matrix = matrix;
		Point start = new Point();
		Point end = new Point(row-1,col-1);
		while(true){
			if(isAllZeroDown(start, row)){
				start.y = start.y+1 >=col ? col-1:start.y+1;
				if(start.equals(end)){
					return 0;
				}
			}
			if(isAllZeroLeft(start, col)){
				start.x = start.x+1 >=row ? row-1:start.x+1;
				if(start.equals(end)){
					return 0;
				}
			}
			
			if(!isAllZeroDown(start, row) && !isAllZeroLeft(start, col)){
				break;
			}
		}
		
		while(true){
			if(isAllZeroRight(end)){
				end.y = end.y-1>= 0 ? end.y-1:0;
			}
			if(isAllZeroUp(end)){
				end.x = end.x-1>= 0 ? end.x-1:0;
			}
			if(!isAllZeroRight(end) && !isAllZeroUp(end)){
				break;
			}
		}
		ans = Math.abs((end.x-start.x+1)*(end.y - start.y+1));
		return ans;
	}
	
	boolean isAllZeroDown(Point p,int len){
		int j = p.y;
		for(int i=p.x;i
  
   =0;j--){
			if(matrix[i][j]=='1'){
				return false;
			}
		}
		return true;
	}
	boolean isAllZeroRight(Point p){
		int j = p.y;
		for(int i=p.x;i>=0;i--){
			if(matrix[i][j]=='1'){
				return false;
			}
		}
		return true;
	}
}
  

提交之后始终不对，然后开始网上搜索，才发现题目正确意思是：

找一个最大矩阵，里面全部是1。

例如下图：

根据这个图转换可以发现问题，看下图：

转到这个图就会发现，这就是：http://blog.csdn.net/huruzun/article/details/39717501里面说到的相同问题。

java代码：

public class Solution {
    	public int largestRectangleArea(int[] height) {
		int maxarea = 0;
		Stack
  
    sta = new Stack<>();
		int top ;
		int top_area;
		int i = 0;
		while(i
   
    maxarea){ maxarea = top_area; } } } while(!sta.isEmpty()){ top = sta.pop(); top_area = height[top] * (sta.isEmpty()? i:i-sta.peek()-1); if(top_area>maxarea){ maxarea = top_area; } } return maxarea; } public int maximalRectangle(char[][] matrix){ if(matrix.length == 0){ return 0; } int row = matrix.length; int col = matrix[0].length; int [][]dp = new int[row][]; for(int i=0;i
    
     maxarea){ maxarea = temp; } } return maxarea; } }