“This is the 23rd day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

The title

Link: leetcode-cn.com/problems/ma…

Given a two-dimensional binary matrix containing only 0 and 1 and size Rows x cols, find the largest rectangle containing only 1 and return its area.

 

Example 1:

Input: * * * * matrix = [[” 1 “, “0”, “1”, “0” and “0”], [” 1 “, “0”, “1”, “1”, “1”], [” 1 “, “1”, “1”, “1”, “1”], [” 1 “, “0”, “0”, “1”, “0”]] output: * * * * * * 6: ** The maximum rectangle is shown in the figure above.

Example 2:

Input: matrix = [] output: **0

Example 3:

Matrix = [[“0”]] ** output: **0

Example 4:

Input: matrix = [[“1”]] output: **1

Example 5:

Matrix = [[“0″,”0”]] ** output: **0

 

Tip:

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

Their thinking

  1. Two-dimensional coordinates are converted into multiple bar charts
    • The column is continuous in two dimensional coordinates'1'
    • Each bar chart has row I moving to the right as the abscissa and column 0 moving up as the ordinate
  2. For each bar graph, find the maximum rectangular area
    • For any column top, find the first column that is strictly lower than itself left/right * Find the first element that is strictly less than/greater than itself from an element in the one-dimensional unordered array left/right * Use monotone stack to implement * In this case, to find an element that is strictly lower than itself, so design monotone stack strictly increasing, when out of the stack, It is easy to find the left/right pillar in O(1) time
    • The area of the rectangle isheights[top] * width , width = (right - 1) - (left + 1) + 1
    • Each as a column top, can challenge to figure out the maximum rectangular area of the bar chart
  3. The maximum rectangular area of each bar graph is challenged to get the maximum rectangular area in two-dimensional coordinates

code

var maximalRectangle = function(matrix) {
  if(! matrix || ! matrix.length || ! matrix[0].length) return 0
  const ROWS = matrix.length, COLS = matrix[0].length
  // heightsList[I][j] = matrix[I];
  // The height of column j in the bar diagram, column is continuous 1
  const MOD = 2 // heightsList[I] relies on heightsList[i-1] forward at most, using a scrollable array to save space
  let heightsList = Array.from({length: MOD}, () = > new Array(COLS))
  let maxArea = 0
  for (let i = 0; i < ROWS; ++i) { // O(ROWS)
    for (let j = 0; j < COLS; ++j) { // O(COLS)
      heightsList[i % MOD][j] = matrix[i][j] === '1' ?
        (i - 1> =0 ? heightsList[(i - 1) % MOD][j] : 0) + 1 :
        0
    }
    maxArea = Math.max(maxArea, getMaxArea(heightsList[i % MOD]))
  }
  // console.log(heightsList)
  return maxArea

  // Find the maximum rectangle area in the bar chart
  // For any column top, find the first column left/right that is strictly below itself
  Height [top] * width
  // width = (right - 1) - (left + 1) + 1
  // Use monotone stack to find the first column left and right, monotone strictly increasing
  function getMaxArea(heights) {
    // NOTICE:
    // Front sentinel: prevent stack empty, prevent out of bounds
    // Post sentinel: Make sure that every element pushed on the stack eventually goes off the stack
    // In strict increments, the front sentry must be smaller than the back sentry, otherwise the back sentry will leave the stack empty, causing the left to be out of bounds
    heights = [-2. heights, -1]
    const N = heights.length
    let maxArea = 0, stack = []
    for (let i = 0; i < N; ++i) { // O(COLS + 2) = O(COLS), because each element goes on and off the stack only once
      while (stack.length) {
        const top = stack[stack.length - 1]
        if (heights[i] > heights[top]) break
        stack.pop()
        const left = stack[stack.length - 1], right = i
        const width = (right - 1) - (left + 1) + 1
        maxArea = Math.max(
          maxArea,
          width * heights[top]
        )
      }
      stack.push(i)
    }
    return maxArea
  }
}
Copy the code