maximal-rectangle.md

85. Maximal Rectangle - 最大矩形

Tags - 题目标签

Description - 题目描述

EN:

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'.

ZH-CN:

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

 

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

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

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

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

 

提示：

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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
golang	0 ms	6 MB	2022/06/06 21:03

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    m, n := len(matrix), len(matrix[0])
    height := make([][]int, m)
    for i := 0; i < m; i++ {
        height[i] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == '0' {
                continue
            }
            if i == 0 {
                height[i][j] = 1
            } else {
                height[i][j] = height[i - 1][j] + 1
            }
        }
    }

    ans := 0
    for _, nums := range height {
        ans = max(ans, largestRectangleInArr(&nums))
    }

    return ans
}

func largestRectangleInArr(heights *([]int)) int {
  maxArea := 0
  leng := len(*heights)
  stack := make([]int, 0)

  for i := 0; i <= leng; i++ {
    for len(stack) > 0 && (i == leng || (*heights)[i] < (*heights)[stack[len(stack) - 1]] ) {
      curIdx := stack[len(stack) - 1]
      stack = stack[:len(stack) - 1]
      height := (*heights)[curIdx]

      var width int
      if len(stack) > 0 {
        width = i - stack[len(stack) - 1] - 1
      } else {
        width = i
      }

      curArea := width * height

      if maxArea < curArea {
        maxArea = curArea
      }
    }

    stack = append(stack, i)
  }

  return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

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

    return a
}

My Notes - 我的笔记

参考官方题解的单调栈法：

复用第84题的一维数组中的最大矩形的单调栈法。

func maximalRectangle(matrix [][]byte) int {
  m, n := len(matrix), len(matrix[0])
  leftContinuous := make([][]int, m)
  for i := range leftContinuous {
    leftContinuous[i] = make([]int, n)
  }

  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if j == 0 {
        leftContinuous[i][j], _ = strconv.Atoi(string(matrix[i][j]))
      } else {
        if matrix[i][j] == '0' {
          leftContinuous[i][j] = 0
        } else {
          leftContinuous[i][j] = leftContinuous[i][j-1] + 1
        }
      }
    }
  }

  col := make([]int, n)
  maxArea := 0

  for j := 0; j < n; j++ {
    for i := 0; i < m; i++ {
      col = append(col, leftContinuous[i][j])
      curArea := largestRectangleInArr(&col)
      if (curArea > maxArea) {
        maxArea = curArea
      }
    }
    col = make([]int, n)
  }

  return maxArea



}

func largestRectangleInArr(heights *([]int)) int {
  maxArea := 0
  leng := len(*heights)
  stack := make([]int, 0)

  for i := 0; i <= leng; i++ {
    for len(stack) > 0 && (i == leng || (*heights)[i] < (*heights)[stack[len(stack) - 1]] ) {
      curIdx := stack[len(stack) - 1]
      stack = stack[:len(stack) - 1]
      height := (*heights)[curIdx]

      var width int
      if len(stack) > 0 {
        width = i - stack[len(stack) - 1] - 1
      } else {
        width = i
      }

      curArea := width * height

      if maxArea < curArea {
        maxArea = curArea
      }
    }

    stack = append(stack, i)
  }

  return maxArea
}