LeetCode:Maximal Rectangle

Maximal Rectangle
Total Accepted: 43628 
Total Submissions: 183613 
Difficulty: Hard
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Subscribe to see which companies asked this question
Hide Tags
 
Array Hash Table Stack Dynamic Programming
Hide Similar Problems
 
(H) Largest Rectangle in Histogram (M) Maximal Square
考え方:
解法は「Largest Rectangle in Histogram」に似ている.
java code:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        
        if(matrix==null || matrix.length==0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[] height = new int[n+1];
        int maxArea = 0;
        
        for(int row = 0;row < m;row++) {
            Stack<Integer> stack = new Stack<>();
            
            for(int col = 0; col <= n; col++) {
                
                if(col < n) {
                    if(matrix[row][col] == '1') height[col]++;
                    else height[col] = 0;
                }
                
                if(stack.isEmpty() || height[col] >= height[stack.peek()])
                    stack.push(col);
                else {
                    while(!stack.isEmpty() && height[col] < height[stack.peek()]) {
                        int tmp = stack.pop();
                        int wid = stack.isEmpty() ? col : col - stack.peek() - 1;
                        maxArea = Math.max(maxArea, height[tmp] * wid);
                    }
                    stack.push(col);
                }
            }
        }
        return maxArea;
    }
}