85.最大矩形

最大矩形

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

示例：

输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出：6

解析

逐行构建柱状图，然后复用第 84 题的单调栈求最大矩形。

var maximalRectangle = function (matrix) {
  if (!matrix.length) return 0;
  const n = matrix[0].length;
  const heights = new Array(n).fill(0);
  let maxArea = 0;
  for (const row of matrix) {
    for (let j = 0; j < n; j++) {
      heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
    }
    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }
  return maxArea;
};

function largestRectangleArea(heights) {
  const stack = [];
  let max = 0;
  heights.push(0);
  for (let i = 0; i < heights.length; i++) {
    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
      const h = heights[stack.pop()];
      const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
      max = Math.max(max, h * w);
    }
    stack.push(i);
  }
  heights.pop();
  return max;
}