线性动态规划：最大矩形 题目描述 给定一个仅包含0和1的二维二进制矩阵，找出其中只包含1的最大矩形，并返回其面积。 例如： 输入：matrix = [ [ "1","0","1","0","0" ], [ "1","0","1","1","1" ], [ "1","1","1","1","1" ], [ "1","0","0","1","0" ] ] 输出：6 解释：最大矩形如右图所示，面积为6。 解题过程 这个问题可以通过将二维问题转化为一维问题来解决。核心思路是逐行处理矩阵，将每一行视为一个直方图的底部，然后计算以当前行为底的最大矩形面积。 步骤1：预处理高度数组 首先，我们需要为每一行构建一个高度数组 heights ，其中 heights[j] 表示从当前行向上连续的1的个数。 对于第一行： 如果matrix[ 0][ j] = "1"，则heights[ j ] = 1 如果matrix[ 0][ j] = "0"，则heights[ j ] = 0 对于后续行(i > 0)： 如果matrix[ i][ j] = "1"，则heights[ j] = heights[ j ] + 1 如果matrix[ i][ j] = "0"，则heights[ j ] = 0 步骤2：计算直方图中的最大矩形 对于每一行的高度数组，我们需要计算该直方图中能形成的最大矩形面积。这可以通过单调栈来解决。 单调栈方法： 初始化一个空栈，用于存储柱子的索引 从左到右遍历每个柱子： 当栈不为空且当前柱子的高度小于栈顶柱子的高度时： 弹出栈顶元素 计算以弹出元素为高的矩形面积 宽度 = 当前索引 - 栈顶索引 - 1（如果栈为空，宽度就是当前索引） 将当前索引入栈 处理栈中剩余的元素 步骤3：整合算法 完整的算法流程： 如果矩阵为空，返回0 初始化高度数组 heights ，长度等于列数，初始值为0 初始化最大面积 maxArea = 0 遍历每一行： a. 更新高度数组 b. 使用单调栈计算当前高度数组的最大矩形面积 c. 更新全局最大面积 返回最大面积 详细示例 以题目中的矩阵为例： 初始状态：heights = [ 0,0,0,0,0 ] 第0行：[ "1","0","1","0","0" ] 更新heights = [ 1,0,1,0,0 ] 计算最大矩形面积：最大面积为1（在位置0或位置2） 第1行：[ "1","0","1","1","1" ] 更新heights = [ 2,0,2,1,1 ] 计算最大矩形面积： 高度2：宽度1 → 面积2 高度1：宽度3 → 面积3 最大面积为3 第2行：[ "1","1","1","1","1" ] 更新heights = [ 3,1,3,2,2 ] 计算最大矩形面积： 高度3：宽度1 → 面积3（位置0） 高度1：宽度5 → 面积5（位置1） 高度3：宽度1 → 面积3（位置2） 高度2：宽度2 → 面积4（位置3） 高度2：宽度1 → 面积2（位置4） 最大面积为6 第3行：[ "1","0","0","1","0" ] 更新heights = [ 4,0,0,3,0 ] 计算最大矩形面积： 高度4：宽度1 → 面积4 高度3：宽度1 → 面积3 最大面积为4 最终最大面积为6。 复杂度分析 时间复杂度：O(m×n)，其中m是行数，n是列数 空间复杂度：O(n)，用于存储高度数组和栈 这种方法通过将二维问题转化为一维直方图问题，巧妙地利用单调栈来高效求解最大矩形面积。