2014年2月19日星期三

LeetCode - 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.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int height[][] = new int[m][n+1];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(matrix[i][j]=='0') {
                    height[i][j] = 0;
                } else if(i==0){
                    height[i][j] = 1;
                } else {
                    height[i][j] = height[i-1][j] + 1;
                }
            }
        }
        int maxArea = 0;
        for(int r=0;r<m;r++) {
            int hei[] = height[r];
            Stack<Integer> stk = new Stack<Integer>();
            for(int i=0;i<hei.length;i++) {
                int h = hei[i];
                if(stk.isEmpty() || h>=hei[stk.peek()]) {
                    stk.push(i);
                } else {
                    int tmp = stk.pop();
                    int area = hei[tmp] * (stk.isEmpty()?i:i-stk.peek()-1);
                    if(area>maxArea) {
                        maxArea = area;
                    }
                    i--;
                }
            }
        }
        return maxArea;
    }
}

没有评论:

发表评论