Question

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

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

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

Constraints:

rows == matrix.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j] is '0' or '1'.

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

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;
        }
    }

}

############

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix[0].length;
        int[] heights = new int[n];
        int ans = 0;
        for (var row : matrix) {
            for (int j = 0; j < n; ++j) {
                if (row[j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            ans = Math.max(ans, largestRectangleArea(heights));
        }
        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        int res = 0, n = heights.length;
        Deque<Integer> stk = new ArrayDeque<>();
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
                right[stk.pop()] = i;
            }
            left[i] = stk.isEmpty() ? -1 : stk.peek();
            stk.push(i);
        }
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
}

// OJ: https://leetcode.com/problems/maximal-rectangle/
// Time: O(MN)
// Space: O(N)
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& A) {
        int M = A.size(), N = A[0].size(), ans = 0;
        vector<int> h(N), nextSmaller(N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                h[j] = A[i][j] == '0' ? 0 : (h[j] + 1);
            }
            stack<int> s;
            for (int j = N - 1; j >= 0; --j) {
                while (s.size() && h[j] <= h[s.top()]) s.pop();
                nextSmaller[j] = s.size() ? s.top() : N;
                s.push(j);
            }
            s = {};
            for (int j = 0; j < N; ++j) {
                while (s.size() && h[j] <= h[s.top()]) s.pop();
                int prevSmaller = s.size() ? s.top() : -1;
                ans = max(ans, (nextSmaller[j] - prevSmaller - 1) * h[j]);
                s.push(j);
            }
        }
        return ans;
    }
};

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        heights = [0] * len(matrix[0])
        ans = 0
        for row in matrix:
            for j, v in enumerate(row):
                if v == "1":
                    heights[j] += 1
                else:
                    heights[j] = 0
            # check for every row
            ans = max(ans, self.largestRectangleArea(heights))
        return ans

    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stk = []
        left = [-1] * n
        right = [n] * n
        for i, h in enumerate(heights):
            while stk and heights[stk[-1]] >= h:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            h = heights[i]
            while stk and heights[stk[-1]] >= h:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))

############

class Solution(object):
  def maximalRectangle(self, matrix):
    """
    :type matrix: List[List[str]]
    :rtype: int
    """

    def histogram(height):
      if not height:
        return 0
      height.append(-1)
      stack = []
      ans = 0
      for i in range(0, len(height)):
        while stack and height[i] < height[stack[-1]]:
          h = height[stack.pop()]
          w = i - stack[-1] - 1 if stack else i
          ans = max(ans, h * w)
        stack.append(i)
      return ans

    ans = 0
    dp = [[0] * len(matrix[0]) for _ in range(0, len(matrix))]
    for i in reversed(range(0, len(matrix))):
      if i == len(matrix) - 1:
        dp[i] = [int(h) for h in matrix[i]]
      else:
        for j in range(0, len(matrix[0])):
          if matrix[i][j] != "0":
            dp[i][j] = dp[i + 1][j] + 1
      ans = max(ans, histogram(dp[i]))
    return ans

func maximalRectangle(matrix [][]byte) int {
	n := len(matrix[0])
	heights := make([]int, n)
	ans := 0
	for _, row := range matrix {
		for j, v := range row {
			if v == '1' {
				heights[j]++
			} else {
				heights[j] = 0
			}
		}
		ans = max(ans, largestRectangleArea(heights))
	}
	return ans
}

func largestRectangleArea(heights []int) int {
	res, n := 0, len(heights)
	var stk []int
	left, right := make([]int, n), make([]int, n)
	for i := range right {
		right[i] = n
	}
	for i, h := range heights {
		for len(stk) > 0 && heights[stk[len(stk)-1]] >= h {
			right[stk[len(stk)-1]] = i
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		} else {
			left[i] = -1
		}
		stk = append(stk, i)
	}
	for i, h := range heights {
		res = max(res, h*(right[i]-left[i]-1))
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    private int MaximalRectangleHistagram(int[] height) {
        var stack = new Stack<int>();
        var result = 0;
        var i = 0;
        while (i < height.Length || stack.Any())
        {
            if (!stack.Any() || (i < height.Length && height[stack.Peek()] < height[i]))
            {
                stack.Push(i);
                ++i;
            }
            else
            {
                var previousIndex = stack.Pop();
                var area = height[previousIndex] * (stack.Any() ? (i - stack.Peek() - 1) : i);
                result = Math.Max(result, area);
            }
        }

        return result;
    }

    public int MaximalRectangle(char[][] matrix) {
        var lenI = matrix.Length;
        var lenJ = lenI == 0 ? 0 : matrix[0].Length;
        var height = new int[lenJ];
        var result = 0;
        for (var i = 0; i < lenI; ++i)
        {
            for (var j = 0; j < lenJ; ++j)
            {
                if (matrix[i][j] == '1')
                {
                    ++height[j];
                }
                else
                {
                    height[j] = 0;
                }
            }
            result = Math.Max(result, MaximalRectangleHistagram(height));
        }
        return result;
    }
}

85 - Maximal Rectangle

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions