大子矩阵(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;}
};
更多推荐
[单调栈]leetcode1727:重新排列后的最大子矩阵(medium)
发布评论