该题与LeetCode84：柱状图中的最大矩形、LeeCode85：最大矩形息息相关。后面我会将这三道题整理到一个系列中。
核心思想就是计算这个矩形的每一层向上 \(1\) 延伸的高度，将每一层作为一个柱状图计算柱状图中的最大矩形。非常类似于LeeCode85：最大矩形的做法。不过不同的是，在上面两题中，高度不能交换位置，所以计算底边长度需要通过单调栈快速计算。本题中可以直接使用排序，排序后矩形的宽度得到最大化，且非常容易计算。
枚举底边＋排序
class Solution {
public:// 相比于不能重新排列的反而简单，直接排序每个可能延申的最大宽度即为从左到当前位置的长度（greater排序）// 如果不能排序需要使用单调栈处理int compute_max(vector<int> row){int ans=0; int n=row.size();sort(row.begin(),row.end(),greater<int>());for(int i=0;i<n;++i){ans=max(ans,row[i]*(i+1));}return ans;}int largestSubmatrix(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<vector<int>> height(m+1,vector<int>(n,0));// 计算向上延申的柱子高度for(int i=1;i<m+1;++i){for(int j=0;j<n;++j){if (matrix[i-1][j]){height[i][j]=height[i-1][j]+matrix[i-1][j];}}}int ans=0;for(auto& row:height){ans=max(ans,compute_max(row));}return ans;}
};
优化
灵神题解中提出了一种优化策略可以优化掉 \(logn\) 的排序。核心思想是，从上到下，每次当前位置不为 \(0\) 的 \(height\) 增加相同的数目，排序不变；当前位置为 \(0\) 的变为 \(0\) 移动至最前方，因为都相等，没必要排序。又有起始层非 \(0\) 即 \(1\) 这样只需要每次都把为 \(0\) 的放在最前端，就统一了初始和每层的操作，不需要排序。不过因为移动会导致无法确定当前位置对应矩形哪个位置，需要创建一个索引，来记录。
优化1
因为在循环中申请内存，实际上很慢。
class Solution {
public:int largestSubmatrix(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<int> height(n,0);vector<int> idx(n);ranges::iota(idx,0);int ans=0;for (int i=0;i<m;++i){// 这里可以优化，在循环中申请内存，很慢vector<int> zero_idx;vector<int> one_idx;for(int j=0;j<n;++j){if (matrix[i][idx[j]]==0){zero_idx.push_back(idx[j]);height[idx[j]]=0;}else{one_idx.push_back(idx[j]);height[idx[j]]+=1;}}// 记录起点int start=zero_idx.size();// 拼接zero_idx.insert(zero_idx.end(),one_idx.begin(),one_idx.end());// 更新排序idxidx=zero_idx;// 从起点开始，零值部分不用计算for (int i=start;i<n;++i){ans=max(ans,height[idx[i]]*(n-i));}}return ans;}
};
优化2
在优化1的基础上在循环外分配内存，不过循环内就需要原地操作，理解起来麻烦了。
class Solution {
public:int largestSubmatrix(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<int> height(n,0);vector<int> idx(n);// 循环外申请内存vector<int> none_zero(n);ranges::iota(idx,0);int ans=0;for (int i=0;i<m;++i){int p=0,q=0;for(int j=0;j<n;++j){if (matrix[i][idx[j]]==0){// idx原地更新零的部分idx[p++]=idx[j];height[idx[j]]=0;}else{// none_zero存储1的部分none_zero[q++]=idx[j];height[idx[j]]+=1;}}// 从起点开始，零值部分不用计算for (int i=p;i<n;++i){// 将1的部分更新到idx中idx[i]=none_zero[i-p];ans=max(ans,height[idx[i]]*(n-i));}}return ans;}
};