[单调栈]leetcode1727：重新排列后的最大子矩阵(medium)

大子矩阵(medium)"/>

[单调栈]leetcode1727：重新排列后的最大子矩阵(medium)

题目：

1727. 重新排列后的最大子矩阵

题解：

• 题解1：本题与85. 最大矩阵相比就多了一个排序，为了贪心的寻找面积的最大值。
• 题解2：与题解1思路差不多，不过是直接对原数组进行操作计算每行每个元素的高度，然后遍历数组，对每行元素(高度)进行排序，贪心地计算面积的最大值。

代码如下：

class Solution {
private:// 维护一个单调递增的栈，也就是 t84 的最大矩形面积int largestRectangleArea(vector<int> heights){// 注意这里要排序一下，因为我们要寻找子矩阵的最大值，所以排序将高度差不多的移动到一块sort(heights.begin(),heights.end());heights.insert(heights.begin(),0);heights.push_back(0);int res=0;stack<int> st;for(int i=0;i<heights.size();++i){// 不满足递增栈了，开始进行弹栈，顺便计算面积while(!st.empty()&&heights[st.top()]>heights[i]){int cur=st.top();st.pop();// heights[i]用不到，因为太矮了，所以右边界只能到i-1；左边界为它自己本身，也就是top+1int left=st.top()+1,right=i-1;res=max(res,(right-left+1)*heights[cur]);}st.push(i);}return res;}
public:// 题解1：本题就是t85的弱鸡版本，奈何本人太菜了周赛时没做出来int largestSubmatrix_1(vector<vector<int>>& matrix) {int n=matrix.size(),m=matrix[0].size();// 将每一列转换为高度vector<int> heights(m,0);int res=0;for(int i=0;i<n;++i){for(int j=0;j<m;++j){heights[j]=matrix[i][j]==1?heights[j]+1:0;}res=max(res,largestRectangleArea(heights));}return res;}// 题解2：枚举+排序，枚举一行中每列的高度，枚举的目的就是为了将二维转换为一维，统计每列的高度// 排序的目的就是为了将题目中的列重新排列，用来计算最大的面积int largestSubmatrix(vector<vector<int>>& matrix){int n=matrix.size(),m=matrix[0].size();// 预处理数组，计算每一行的高度for(int i=1;i<n;++i)for(int j=0;j<m;++j)if(matrix[i][j])matrix[i][j]+=matrix[i-1][j];// 计算最大面积int res=0;for(int i=0;i<n;++i){// 这个排序是为了贪心，将高度由低到高排序为了计算最大面积sort(matrix[i].begin(),matrix[i].end());// 从每行倒序计算最大面积，j-m为矩形的宽度for(int j=m-1;j>=0;j--){int height=matrix[i][j];res=max(res,height*(m-j));}}return res;}
};