柱状图中的最大矩形

单调栈如何求柱状图中的最大矩形？

• 结论 (84): 最大矩形的高度一定等于某根柱子的高度;
• 转化: 对每根柱子 i, 找出左侧第一个更矮的 left 与右侧第一个更矮的 right, 面积即 height[i] * (right - left - 1);
• 做法: 维护单调递减栈; 当前柱更矮时弹出栈顶 mid, right = i、left = 弹出后的新栈顶;
• 边界: 首尾各补一个 0, 让所有柱子都能被弹出而不必特判;
• 时间 $O(n)$, 空间 $O(n)$;

const largestRectangleArea = (heights) => {
  heights.push(0);
  heights.unshift(0);

  let res = 0;
  const stack = [];
  for (let i = 0; i < heights.length; i++) {
    while (stack.length && heights[i] < heights[stack.at(-1)]) {
      const mid = stack.pop();
      res = Math.max(res, heights[mid] * (i - stack.at(-1) - 1));
    }
    stack.push(i);
  }
  return res;
};

二维矩阵中的最大全 1 矩形如何归约？

• 归约 (85): 以第 i 行为基线, 统计每列自基线向上连续 1 的个数, 得到一组柱高;
• 复用: 对每一行调用一维的柱状图最大矩形, 取最大值;
• 预处理: heightList[i][j] = matrix[i][j] === "1" ? heightList[i-1][j] + 1 : 0;
• 时间 $O(mn)$, 空间 $O(mn)$;

const maximalRectangle = (matrix) => {
  const m = matrix.length;
  const n = matrix[0].length;
  const heightList = Array.from({ length: m }, () => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0) heightList[i][j] = Number(matrix[i][j]);
      else if (matrix[i][j] === "1") heightList[i][j] = heightList[i - 1][j] + 1;
    }
  }

  let res = 0;
  for (let i = 0; i < m; i++) {
    res = Math.max(res, largestRectangleArea(heightList[i].slice()));
  }
  return res;
};