Question

Formatted question description: https://leetcode.ca/all/85.html

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.

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

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

@tag-stack

Algorithm

This question is an extension of the previous 84. Largest Rectangle in Histogram. The two-dimensional matrix of this question can be seen as a histogram at each level upwards.

For each histogram to call the method in 84. Largest Rectangle in Histogram to get the largest rectangle area.

Then the only thing to do in this question is to treat each layer as the bottom layer of the histogram, and construct the entire histogram upwards. Since the question limits the characters of the input matrix to only ‘0’ and ‘1’, it is processed It is also relatively simple. The method is, for each point, if it is ‘0’, assign 0, if it is ‘1’, assign the previous height value plus 1.

Code

Java

import java.util.Arrays;
import java.util.Stack;

public class Solution {
        public int maximalRectangle(char[][] m) {
            /*
	        original:

	        "0010",
	        "1111",
	        "1111",
	        "0111",
	        "1100",
	        "1111",
	        "1110"

	        */



	    	/*
			"01101",
			"11010",
			"01110",
			"11110",
			"11111",
			"00000",


			[0, 1, 1, 0, 1],
			[1, 2, 0, 1, 0],
			[0, 3, 1, 2, 0],
			[1, 4, 2, 3, 0],
			[2, 5, 3, 4, 1],
			[0, 0, 0, 0, 0]]
		*/

            if (m == null || m.length == 0) {
                return 0;
            }


            int row = m.length;
            int col = m[0].length;

            // build dp, dp[i][j]就是当前的第j列的,从上面开始到第i行连续1的个数
            int[][] dp = new int[row][col];

            // process first row
            for (int j = 0; j < col; j++) {
                dp[0][j] = m[0][j] - '0';
            }

            //@note: assumption, at least 2 rows
            for (int i = 1; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (m[i][j] - '0' != 0) {
                        dp[i][j] = 1 + dp[i - 1][j];
                    }
                }
            }

            if (m.length == 1) {
                return findRowMax(dp[0]);
            }


            // search each row of dp array
            int max = 0;
            for (int i = 0; i < row; i++) {
                int rowMax = findRowMax(dp[i]);
                max = max > rowMax ? max : rowMax;
            }

            return max;
        }

        public int findRowMax(int[] rowOriginal) {

            int[] row = new int[rowOriginal.length + 1];
            row = Arrays.copyOfRange(rowOriginal, 0, rowOriginal.length + 1);

            int max = 0;
            int length = row.length;

            // stack store index, not the actual value
            Stack<Integer> sk = new Stack<>();
            int i = 0;
            while (i < length) {
                // if (i == 0 || row[i] >= row[sk.peek()]) {
                if (sk.isEmpty() || row[i] >= row[sk.peek()]) {
                    sk.push(i);
                    i++;
                } else {

                    // while (!sk.isEmpty() && row[i] < row[sk.peek()]) {

                    //     int index = sk.pop();
                    //     int prevIndex = sk.isEmpty()? 0 : sk.peek();

                    //     int area = (i - 1 - prevIndex) * row[index]; // i-1 is the highest bar before i
                    //     max = max > area ? max : area;

                    // }

                    int index = sk.pop();
                    // int prevIndex = sk.isEmpty()? 0 : sk.peek();
                    // int prevIndex = sk.isEmpty() ? i : sk.peek();

                    // 这里是:高度(row[index]) * 长度
                    int area = (sk.isEmpty() ? i : (i - 1 - sk.peek())) * row[index]; // i-1 is the highest bar before i
                    max = max > area ? max : area;

                    // sk.push(i++);
                }
            }

            // final check when reaching end of array. OR add dummy number to array end
            // while (!sk.isEmpty()) {

            //     int index = sk.pop();
            //     int prevIndex = sk.isEmpty()? 0 : sk.peek();

            //     int area = (i - 1 - prevIndex) * row[index]; // i-1 is the highest bar before i
            //     max = max > area ? max : area;
            // }

            return max;
        }
    }

}

All Problems

All Solutions