题目链接

力扣

题目描述

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

示例 1：

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。
示例 2：

输入：matrix = []
输出：0
示例 3：

输入：matrix = ["0"]
输出：0
示例 4：

输入：matrix = ["1"]
输出：1
示例 5：

输入：matrix = ["00"]
输出：0
 

提示：

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

解题思路

此题可以在上一题的基础上做，把每一行单独处理，下一行的每个元素如果符合：

1、当前元素不为0

2、上一行对应位置元素不为0

的情况下就可以把上一行的元素加到本行

代码

Python

class Solution:
    def maximalRectangle(self, matrix: list[str]) -> int:
        def largestRectangleArea(heights: list[int]) -> int:
            stack = []
            stack.append(0)
            heights.insert(0, 0)
            heights.append(0)
            maxArea = 0
            for i in range(1, len(heights)):
                while heights[stack[-1]] > heights[i]:
                    height = heights[stack.pop()]
                    width = i - stack[-1] - 1
                    maxArea = max(maxArea, height * width)
                stack.append(i)
            return maxArea
        if not matrix:
            return 0
        newMatrix = [[0 for _ in range(len(matrix[0]))]]
        for row in range(len(matrix)):
            rowlist = list(matrix[row])
            rowlist = [int(x) for x in rowlist]
            for i in range(len(rowlist)):
                if newMatrix[row][i] != 0 and rowlist[i] != 0:
                    rowlist[i] += newMatrix[row][i]
            newMatrix.append(rowlist)
        maxArea = 0
        for i in range(1, len(newMatrix)):
            maxArea = max(maxArea, largestRectangleArea(newMatrix[i]))
        return maxArea

Go

type stack []int
 
func (s *stack) push(i int) {
	*s = append(*s, i)
}
 
func (s *stack) pop() int {
	a := *s
	i := a[len(a)-1]
	*s = a[:len(a)-1]
	return i
}
 
func (s *stack) top() int {
	a := *s
	return a[len(a)-1]
}
 
func largestRectangleArea(heights []int) int {
	var stack stack
	addDummy := make([]int, len(heights)+2)
	for i := 0; i < len(heights); i++ {
		addDummy[i+1] = heights[i]
	}
	heights = addDummy
	stack.push(0)
	maxArea := 0
	for i := 1; i < len(heights); i++ {
		for heights[stack.top()] > heights[i] {
			height := heights[stack.pop()]
			width := i - stack.top() - 1
			if height*width > maxArea {
				maxArea = height * width
			}
		}
		stack.push(i)
	}
	return maxArea
}
 
func intMatrix(matrix []string) [][]int {
	zero := make([]int, len(matrix[0]))
	ans := [][]int{zero}
	for _, s := range matrix {
		tmp := []int{}
		for i := 0; i < len(s); i++ {
			tmp = append(tmp, int(s[i]-'0')) //必须减'0'因为go中都用uint8存储字符
		}
		ans = append(ans, tmp)
	}
	return ans
}
 
func maximalRectangle(matrix []string) int {
	if len(matrix) == 0 {
		return 0
	}
	intMatrix := intMatrix(matrix)
	for row := 1; row < len(intMatrix); row++ {
		for k, v := range intMatrix[row] {
			if intMatrix[row][k] != 0 && intMatrix[row-1][k] != 0 {
				intMatrix[row][k] = v + intMatrix[row-1][k]
			}
		}
	}
	maxArea := 0
	for i := 1; i < len(intMatrix); i++ {
		size := largestRectangleArea(intMatrix[i])
		if size > maxArea {
			maxArea = size
		}
	}
	return maxArea
}