欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[单调栈]leetcode85:最大矩阵(hard)

程序员文章站 2022-07-07 18:55:47
...

题目:
[单调栈]leetcode85:最大矩阵(hard)
题解:

  • 单调栈
  • 本题在84. 柱状图中最大的矩形的基础上对每一行都求出每个元素对应的高度,这个高度就是对应的连续1的长度,然后对每一行都更新一次最大矩形面积。那么这个问题就变成了Largest Rectangle in Histogram。本质上是对矩阵中的每行,均依次执行84题算法。

代码如下:

class Solution {
private:
    //利用84题最大矩阵的解法:单调栈
    int largestRectangleArea(vector<int>& heights){
        /*if(heights.empty())return 0;
        //1、首尾数组首尾加0
        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();
//i-top-1表示矩形的宽,其中top表示height[cur]之前有top个元素需要减去,-1表示i所指向的元素也需要减去,heights[cur]表示矩形的高
                res=max(res,(i-st.top()-1)*heights[cur]);
            }
            st.push(i);
        }
        return res;*/
        //换用下面的代码,避免对heights进行修改
        stack<int> pos; // MaxStack
        int mx=0, i=0;
        for(heights.push_back(0); i<heights.size(); pos.push(i++)){
            while(pos.size() && heights[pos.top()]>heights[i]){
                int h=heights[pos.top()];//获得矩形的高
                pos.pop();
                //i-pos.top()-1表示为矩阵的宽
                mx=max(mx,pos.size()?(i-pos.top()-1)*h:i*h);
            }
        }
        return mx;
    }
public:
    //题解:本题与上一题一样的,不过需要对每一行求出元素对应的高度
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()||matrix[0].empty())return 0;
        int m=matrix.size(),n=matrix[0].size(),area=0;
        vector<int> heights(n,0);//共有n列,计算每行元素对应的高度
        for(auto row:matrix){
            for(int i=0;i<n;++i){
                //若该行的i列元素为1,那么它的高度为上一行对应高度+1;若该行的i列元素不为1,那么它的高度为0
                //对于第一行可以看作在第0行的基础上,进行高度的累加
                heights[i]=row[i]=='1'?heights[i]+1:0;
            }
            area=max(area,largestRectangleArea(heights));
        }
        return area;
    }
};