LeetCode 85: 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 asking "Maximal Square", refer to http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
        
        // For this question, we firstly construct a "Height Matrix" H[][].
        // H[i][j] represents the height of histogrm (matrix[i][j] is the bottom).
        // After that, call the method of "Largest Rectangle in Histogram" to process H[][].
        int m = matrix.length;
        
        if (m == 0)
            return 0;
            
        int n = matrix[0].length;

        // Step 1: Construct H[][]
        int[][] H = new int[m][n];
        
        for (int j = 0; j < n; j++)
            H[0][j] = matrix[0][j]-'0';
        
        for (int i = 1; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == '1')
                    H[i][j] = H[i-1][j] + 1;
                else
                    H[i][j] = 0;
                    
        // Step 2: Call method of "Largest Rectangle in Histogram" to process H[][]
        int maxArea = 0;
        
        for (int i = 0; i < m; i++)
        {
            int tmp = largestRectangleArea(H[i]);
            
            if (tmp > maxArea)
                maxArea = tmp;
        }
        
        return maxArea;
    }
    
    // Method of "Largest Rectangle in Histogram"
    public int largestRectangleArea(int[] height)
    {
        Stack<Integer> stack = new Stack<>();
        
        int maxArea = 0;
        int i = 0;
        
        while (i < height.length)
        {
            if (stack.isEmpty() || height[i]>height[stack.peek()])
            {
                stack.push(i);
                i++;
            }
            else
            {
                int tmp = stack.pop();
                maxArea = Math.max(maxArea, height[tmp] * (stack.isEmpty() ? i : i-stack.peek()-1));
            }
        }
        
        // Don't miss the last bar as the smallest bar.
        // Special case: If "height" is an ascending array, the largest rectangle area is the area of last bar.
        while (!stack.isEmpty())
        {
            int tmp = stack.pop();
            maxArea = Math.max(maxArea, height[tmp] * (stack.isEmpty() ? i : i-stack.peek()-1));
        }         
        
        return maxArea;        
    }
}