本文共 3203 字，大约阅读时间需要 10 分钟。

题目概述

本题可以看作是复杂版的 Leetcode 84 Largest Rectangle in Histogram（最大的矩形面积）。我们需要将原始矩阵转换为每个位置的柱状图高度，然后利用最大柱状图方法计算每层的最大矩形面积，最后比较各层的面积，得出整体最大值。

解题思路

本题可以采用以下两种思路之一： 第一种思路： 将原始矩阵转换为每个位置的柱状图高度。具体方法是：

创建一个辅助矩阵 calc，用于记录每个位置的柱状图高度。

从矩阵中逐行处理，计算每个位置的柱状图高度。具体步骤如下：

• 初始化 calc 矩阵，calc[i][j] 代表第 i 行第 j 列的柱状图高度。
• 如果当前位置是 0，则 calc[i][j] 设为 0。
• 否则，calc[i][j] 设为 1，再加上上层的高度（如果存在的话）。

对转换后的 calc 矩阵，使用最大柱状图算法计算每个柱状图的最大矩形面积。

第二种思路：

采用动态规划的思路，虽然具体实现细节与第一种方法较为相似，但核心思想是通过逐层累加高度来计算最大矩形面积。

算法性能

采用最大柱状图的单调栈方法，时间复杂度为 O(M*N)，空间复杂度为 O(N)。该算法通过维护一个递减栈，记录当前柱状图的左边界和右边界，从而高效计算出每个柱状图的最大矩形面积。

代码示例

以下是基于单调栈方法的代码实现：

public class Solution {
    public int maximalRectangle(vector
   
    
     > matrix) {
        if (matrix.size() == 0) {
            return 0;
        }
        int lenRow = matrix.size();
        int lenCol = matrix[0].size();
        int maxArea = 0;
        // 创建辅助矩阵
        int[][] calc = new int[lenRow][lenCol + 2];
        for (int i = 0; i < lenRow; i++) {
            calc[i] = new int[lenCol + 2];
            for (int j = 0; j < lenCol + 2; j++) {
                calc[i][j] = -lenCol * 2 + j;
            }
        }
        for (int ri = 0; ri < lenRow; ri++) {
            for (int ci = 1; ci <= lenCol; ci++) {
                calc[ri][ci] = (matrix[ri][ci - 1] == '0') ? 0 : 1;
                if (ri > 0 && calc[ri][ci] > 0 && calc[ri - 1][ci] > 0) {
                    calc[ri][ci] += calc[ri - 1][ci];
                }
            }
        }
        // 使用单调栈计算最大矩形面积
        int[] rectStart = new int[lenCol + 2];
        int[] rectEnd = new int[lenCol + 2];
        ArrayFill(rectStart, 0, lenCol + 2);
        ArrayFill(rectEnd, 0, lenCol + 2);
        for (int ri = 0; ri < lenRow; ri++) {
            Deque
     
       stack = new ArrayDeque<>();
            for (int ci = 0; ci < lenCol + 2; ci++) {
                int current = calc[ri][ci];
                if (stack.isEmpty()) {
                    stack.push(ci);
                    rectStart[ci] = stack.peek();
                    rectEnd[ci] = ci;
                } else {
                    int tempTop = stack.peek();
                    if (current > calc[ri][tempTop]) {
                        stack.push(ci);
                        rectStart[ci] = tempTop;
                        rectEnd[ci] = ci;
                    } else {
                        while (!stack.isEmpty() && calc[ri][tempTop] > current) {
                            int top = stack.pop();
                            rectEnd[top] = ci;
                            int width = rectEnd[top] - rectStart[top] - 1;
                            int height = calc[ri][top];
                            int area = width * height;
                            if (area > maxArea) {
                                maxArea = area;
                            }
                        }
                        stack.push(ci);
                        rectStart[ci] = stack.peek();
                    }
                }
            }
        }
        return maxArea;
    }
    // 初始化数组
    private void ArrayFill(int[] array, int value, int length) {
        Arrays.fill(array, value);
    }
}
     
    
   

以上代码基于单调栈方法，通过维护一个递减栈来高效计算每个柱状图的最大矩形面积，时间复杂度为 O(M*N)，空间复杂度为 O(N)。

转载地址：http://wesm.baihongyu.com/