POJ-3494 Largest Submatrix of All 1’s

Largest Submatrix of All 1’s

单调栈

感觉很经典的题目，不知道为啥就没做出来

从第 \(i\) 行来说，\(a_{ij}\) 可以抽象成一个高度为 \(x\) 的山峰，\(x\) 取决于在第 \(j\) 列，从第 \(i\) 行开始往上数，有多少个连续的 \(1\)

4 4
0 1 0 1
0 1 1 0
1 1 1 0
0 0 0 0

例如对于第三行来说，他就可以抽象成一个数组

1 3 2 0

问题就转换成，对于每一行这样的一个数组，找一个 \([l, r]\) 使得区间内元素都不小于 \(y\)，并且 \((r - l + 1) * y\) 最大

这样的话就可以用单调栈来做，对于每个点，假设当前那个点的值就是 \(y\)，尽可能的找到最小的 \(l\) 和 最大的 \(r\)

不断取找最大值就行了

复杂度 \(O(n^2)\)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;
const int maxn = 2e3 + 10;
int a[maxn], r[maxn], l[maxn];

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF && (n | m))
    {
        for(int i=1; i<=m; i++) a[i] = 0;
        int ans = 0;
        a[0] = a[m + 1] = -1;
        for(int i=0; i<n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                int x;
                scanf("%d", &x);
                if(x) a[j] += 1;
                else a[j] = 0;
            }
            stack<int>st;
            st.push(0);
            for(int i=1; i<=m; i++)
            {
                while(st.size() && a[st.top()] >= a[i]) st.pop();
                l[i] = st.top();
                st.push(i);
            }
            while(st.size()) st.pop();
            st.push(m + 1);
            for(int i=m; i>=1; i--)
            {
                while(st.size() && a[st.top()] >= a[i]) st.pop();
                r[i] = st.top();
                st.push(i);
            }
            for(int i=1; i<=m; i++)
                ans = max(ans, (r[i] - l[i] - 1) * a[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}