最大子矩阵

类似于面试题17.24;

不过是每个单元的元素只是一,可以把问题转化为求取面积。

直接用单调栈求取从一个柱子可扩展的的最大面积即可。

代码

#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;
int n , m;
vector<int> height;
int maxarea = 0;

void caculateArea(vector<int>&area){
    for(int i = 0; i < area.size(); ++i){
        if(area[i]) height[i] += area[i];
        else height[i] = 0;

    }
    stack<int> st;
    height.push_back(0);
    
    for(int i = 0; i < height.size(); ++i){

        while(st.size() && height[st.top()] >= height[i]){
            int hei = height[st.top()];
            st.pop();
            int l = st.size() ? st.top() : -1;
            maxarea = max(maxarea, (i - 1 - l)* hei);
          //  cout << l << ' ' << maxarea << ' ' << i - 1  << ' ' << hei<< endl;

        }
        st.push(i);
    }
    height.erase(height.end() - 1);
    
}


int main(){
    cin >> n  >> m;
    vector<int> maze(m);
    height.resize(m);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j) cin >> maze[j];
        caculateArea(maze);
    }
    cout << maxarea << endl;
    return 0;
}

Comments