Medium

题目描述

给你一个大小为 m x n 的二进制矩阵 matrix，你可以任意重新排列矩阵的列。

在最优地重新排列列后，返回 matrix 中全部元素都是 1 的最大子矩阵的面积。

示例 1：

输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按如上所示重新排列列。
全部元素都是 1 的最大子矩阵（用粗体标出）的面积为 4。

示例 2：

输入：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按如上所示重新排列列。
全部元素都是 1 的最大子矩阵（用粗体标出）的面积为 3。

示例 3：

输入：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：注意你必须重新排列整个列，没有办法让全部元素都是 1 的子矩阵面积超过 2。

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m * n <= 10^5
  • matrix[i][j] 要么是 0，要么是 1

提示：

  • 对于每一列，找到每个位置结尾的连续 1 的数量。
  • 对于每一行，将累计的 1 按非递增顺序排序，并"适合"最大的子矩阵。

解题思路

这道题的关键洞察是：由于我们可以任意重新排列列，所以对于固定的行作为矩形底边，我们要找的是在这一行上能形成的最大矩形面积。

解题思路：

  1. 预处理阶段：对于每一列，计算从上往下每个位置结尾的连续1的个数（即高度）。如果当前位置是0，则高度为0；如果是1，则高度为上一行该列的高度+1。

  2. 贪心策略：对于每一行，我们获得了该行每列对应的"高度"数组。由于可以任意重排列，我们将高度数组按降序排序。

  3. 计算最大面积：排序后，对于位置i（0-indexed），我们可以取前i+1个柱子组成矩形，高度为第i个柱子的高度，宽度为i+1。遍历所有可能的宽度，取最大面积。

这个算法的核心思想是将问题转化为"柱状图中的最大矩形"变种。通过重排列的特性，我们可以贪心地选择最优的列组合。

时间复杂度为O(m×n×log n)，空间复杂度为O(n)。

代码实现

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int maxArea = 0;
        
        // 计算每列从上到下的连续1的高度
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i-1][j];
                }
            }
        }
        
        // 对每一行进行处理
        for (int i = 0; i < m; i++) {
            vector<int> heights = matrix[i];
            sort(heights.begin(), heights.end(), greater<int>());
            
            for (int j = 0; j < n; j++) {
                maxArea = max(maxArea, heights[j] * (j + 1));
            }
        }
        
        return maxArea;
    }
};

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        max_area = 0
        
        # 计算每列从上到下的连续1的高度
        for i in range(1, m):
            for j in range(n):
                if matrix[i][j] == 1:
                    matrix[i][j] += matrix[i-1][j]
        
        # 对每一行进行处理
        for i in range(m):
            heights = matrix[i][:]
            heights.sort(reverse=True)
            
            for j in range(n):
                max_area = max(max_area, heights[j] * (j + 1))
        
        return max_area

public class Solution {
    public int LargestSubmatrix(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        int maxArea = 0;
        
        // 计算每列从上到下的连续1的高度
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i-1][j];
                }
            }
        }
        
        // 对每一行进行处理
        for (int i = 0; i < m; i++) {
            int[] heights = new int[n];
            Array.Copy(matrix[i], heights, n);
            Array.Sort(heights, (a, b) => b.CompareTo(a));
            
            for (int j = 0; j < n; j++) {
                maxArea = Math.Max(maxArea, heights[j] * (j + 1));
            }
        }
        
        return maxArea;
    }
}

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var largestSubmatrix = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    // Calculate heights for each position
    for (let i = 1; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 1) {
                matrix[i][j] += matrix[i-1][j];
            }
        }
    }
    
    let maxArea = 0;
    
    // For each row, sort heights and calculate max area
    for (let i = 0; i < m; i++) {
        const heights = matrix[i].slice().sort((a, b) => b - a);
        
        for (let j = 0; j < n; j++) {
            const area = heights[j] * (j + 1);
            maxArea = Math.max(maxArea, area);
        }
    }
    
    return maxArea;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n × log n)预处理需要O(m×n)，每行排序需要O(n log n)，共m行
空间复杂度O(n)需要额外数组存储每行的高度进行排序

相关题目