Skip to main content

最大矩形

Tips

题目类型: 单调栈

相关题目:

题目​

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

提示:
  • rows == matrix.length
  • cols == matrix[0].length
  • 1 <= rows, cols <= 200
  • matrix[i][j] 为 0 或 1
示例

85-maximal-rectangle

输入: matrix = [[4, 0, 0, 3, 0], [3, 1, 3, 2, 2], [2, 0, 2, 1, 1], [1, 0, 1, 0, 0]]

输出: 6

解释: 最大矩形如上图所示.

题解​

本题的要点是想办法把二维矩阵变成如下方式:

以最后一行 row 为底, 可以得到 heights 为 [4, 0, 0, 3, 0].

85-maximal-rectangle

以倒数第二行 row 为底, 可以得到 heights 为 [3, 1, 3, 2, 2.

85-maximal-rectangle

以此类推, 我们得到一组 heights. 这样我们用 84. 柱状图中最大的矩形 的方法, 计算每组 heights 的最大面积, 最终取最大值即可.

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function (matrix) {
  const m = matrix.length
  const n = matrix[0].length

  const allHeights = []
  for (let i = m - 1; i >= 0; i--) {
    const heights = []

    for (let j = 0; j < n; j++) {
      let count = 0

      for (let k = i; k >= 0; k--) {
        if (matrix[k][j] === '1') {
          count++
        } else {
          break
        }
      }

      heights.push(count)
    }

    allHeights.push(heights)
  }

  let max = 0
  for (const heights of allHeights) {
    max = Math.max(max, largestRectangleArea(heights))
  }

  return max
}

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
  const n = heights.length
  const left = new Array(n).fill(-1)
  const right = new Array(n).fill(n)
  const stack = []

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      right[stack.pop()] = i
    }

    stack.push(i)
  }

  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      left[stack.pop()] = i
    }

    stack.push(i)
  }

  let max = 0

  for (let i = 0; i < n; i++) {
    const height = heights[i]
    const leftIdx = left[i]
    const rightIdx = right[i]
    max = Math.max(max, (rightIdx - leftIdx - 1) * height)
  }

  return max
}