重新排列后的最大子矩阵 图解题解

整列搬动之后，全 1 矩形最大能有多大

给一个 m 行 n 列、只装 0 和 1 的矩阵 matrix，你能把任意几列整列换位置，但一列里的上下格子必须原样跟着走。问重排之后全是 1 的矩形面积最大是多少。题面 matrix=[[0,0,1],[1,1,1],[1,0,1]] 把带 1 的列凑一起能框出 2 乘 2 全 1 块，面积 4；单行 matrix=[[1,0,1,0,1]] 把三个 1 挪到相邻，是一条长 3 的横条。

列能排出 n 的阶乘种顺序，挨个试排不动

n 列能排出 n 的阶乘那么多种顺序，枚举每种排法找矩形根本跑不完。但重排只挪列的左右位置，从没打乱过一列内部的上下关系——正因为列内锁死，一个格子向上连着几个 1，是重排前后都不变的量。抓住这个不变量，二维搬列就能拆成一行行分开算。

压高度：把每列连续的 1 累成一个数

第一步压高度，也就是把每列向上连续的 1 累成一个高度值：格子是 0 就记 0，是 1 就等于正上方那格的高度再加 1。压完，每列成了一根固定高度的柱子，重排列就是把这排柱子随意挪位置。

第二步在每行里数矩形。柱子能随便摆，最省的摆法就是把用到的柱子从高到低挨在一起。把这行高度从大到小排好，站在从左数第 j 根柱子上，它连同左边一共 j 根都不比它矮，恰好托起高等于它、宽等于 j 的矩形，面积就是 j 乘这根的高度，逐根取最大即可。

矩形的高，为什么取当前这根而不是最高那根

排完序，第 j 根柱子是左边这 j 根里最矮的一根。矩形要全是 1，高就被最矮那根卡死，矩形高只能取它自己、宽取 j。若图省事拿这片里的最高值当高，上半截会戳进矮柱子的 0 空当，矩形就不再全是 1。

拿题面 3 乘 3 矩阵逐格演一遍

先压高度。第 0 行在最顶上、没得接，原样 0、0、1。第 1 行都是 1，正上方高度 0、0、1 各加 1 得 1、1、2。第 2 行原始 1、0、1：头一个正上方 1 加 1 得 2，中间 0 记 0，末一个正上方 2 加 1 得 3，压成 2、0、3。

再一行行排序数矩形。第 0 行排成 1、0、0，第 1 根 1 乘 1 得 1，后两根空柱记 0。第 1 行排成 2、1、1，第 1 根 2 乘 1 得 2，第 2 根 1 乘 2 得 2，第 3 根 1 乘 3 得 3。第 2 行排成 3、2、0，第 1 根 3 乘 1 得 3，第 2 根 2 乘 2 得 4，第 3 根归零。三行各自最大是 1、3、4，取最大答案 4。

忘了清零、省掉排序，矩形就立不住

压高度扫一遍矩阵是 O(m 乘 n)；数矩形每行给 n 个高度排序，单行 O(n 乘 log n)，m 行合计 O(m 乘 n 乘 log n)，排序是主导项。高度原地压在输入 matrix 上、没另开表，辅助只有常数变量，不计排序内部空间 O(1)。

两处一错就前功尽弃：压高度时忘了本身 0 的格子清零，高度虚高，量出的矩形混进 0；每行省掉排序、按原列序扫，宽度里可能夹根矮柱子，全 1 矩形立不住。边界也想清：全 0 矩阵面积 0；单行 1、0、1、0、1 排序后三根 1 相邻，得长 3 的横条。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        for i in range(1, len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]:
                    matrix[i][j] = matrix[i - 1][j] + 1
        ans = 0
        for row in matrix:
            row.sort(reverse=True)
            for j, v in enumerate(row, 1):
                ans = max(ans, j * v)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j]) {
                    matrix[i][j] = matrix[i - 1][j] + 1;
                }
            }
        }
        int ans = 0;
        for (auto& row : matrix) {
            sort(row.rbegin(), row.rend());
            for (int j = 0; j < n; ++j) {
                ans = max(ans, (j + 1) * row[j]);
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        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] + 1;
                }
            }
        }
        int ans = 0;
        for (int[] row : matrix) {
            Arrays.sort(row);
            for (int j = n - 1, k = 1; j >= 0 && row[j] > 0; --j, ++k) {
                int s = row[j] * k;
                ans = Math.max(ans, s);
            }
        }
        return ans;
    }
}