问题描述

给定一个由 '0' 和 '1' 组成的二维矩阵，找出只包含 '1' 的最大矩形的面积。

解法一

解题思路:

我们可以使用单调栈的方法来解决这个问题。首先，我们将二维矩阵转换为一维数组，然后使用单调栈来找到每个位置的左右边界，最后计算面积。

/** @lc app=leetcode.cn id=85 lang=javascript** [85] Maximal Rectangle*/// @lc code=start
function maximalRectangle(matrix) {if (matrix.length === 0 || matrix[0].length === 0) return 0;let m = matrix.length, n = matrix[0].length;let heights = new Array(n).fill(0);let ans = 0;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {heights[j] = matrix[i][j] === '0' ? 0 : heights[j] + 1;}let stack = [-1];for (let k = 0; k < n + 1; k++) {while (heights[k] < heights[stack[stack.length - 1]]) {let h = heights[stack.pop()];let w = k - 1 - stack[stack.length - 1];ans = Math.max(ans, h * w);}stack.push(k);}}return ans;
}
// @lc code=end