题意分析

本题要求在给定的m×n的0-1矩阵中，找出元素全为1的最大子矩阵，并输出其元素个数。子矩阵的定义是连续的行和连续的列组成的矩阵，最大指的是元素数量最多。如果矩阵全为0，则输出0。

解题思路

核心方法：单调栈优化的直方图最大面积算法

该问题可转化为“直方图最大面积”问题的扩展：

1. 行压缩处理：将每一行视为直方图的基底，计算每一列从当前行向上连续1的高度。
2. 直方图最大面积：对于每一行的高度数组，使用单调栈快速计算以当前行为底的最大矩形面积。
3. 全局最大值：遍历所有行，取各直方图最大面积的最大值作为最终结果。

算法步骤

1. 行压缩：对于每一行，计算每个位置(i,j)向上连续1的高度h[j]，若当前位置为0则高度重置为0。
2. 单调栈计算：使用单调递增栈维护高度数组的索引，栈中元素对应的高度递增。
   • 当遇到比栈顶高度小的元素时，弹出栈顶元素计算以该高度为高的矩形面积。
   • 面积公式：(当前列 - 弹出后栈顶列) × 弹出高度。
3. 更新最大值：遍历所有行的直方图最大面积，取最大值作为结果。

###标程

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
using namespace std;

int main() {
    int i, j, m, n, x, top, tmp, ans, h[2020], a[2020];
    stack<int> st;  // 单调栈，存储列索引，对应高度递增
    
    while (~scanf("%d%d", &m, &n)) {
        ans = 0;
        memset(h, 0, sizeof(h));  // 初始化高度数组（处理第一行）
        
        for (i = 0; i < m; i++) {  // 遍历每一行
            for (j = 1; j <= n; j++) {  // j从1开始便于后续处理
                scanf("%d", &x);
                if (x == 1)
                    h[j] = h[j] + 1;  // 连续1的高度累加
                else
                    h[j] = 0;  // 遇到0，高度重置为0
                a[j] = h[j];  // a数组用于单调栈计算
            }
            a[n+1] = -1;  // 末尾设为-1，确保栈中元素全部出栈
            
            for (j = 1; j <= n + 1; j++) {
                if (st.empty() || a[j] >= a[st.top()]) {
                    st.push(j);  // 栈空或当前高度≥栈顶，直接入栈
                } else {
                    while (!st.empty() && a[j] < a[st.top()]) {
                        top = st.top();
                        st.pop();
                        tmp = (j - top) * a[top];  // 计算面积
                        if (tmp > ans) ans = tmp;  // 更新最大面积
                    }
                    st.push(top);  // 延伸最后弹出的索引
                    a[top] = a[j];  // 修改高度为当前高度
                }
            }
            while (!st.empty()) st.pop();  // 清空栈，处理下一行
        }
        printf("%d\n", ans);
    }
    return 0;
}

关键步骤说明

1. 行压缩处理：
   h[j]表示第j列从当前行向上连续1的高度。例如，对于矩阵：

   0 1 1 0  
   0 1 1 0  
   

   第一行的h为[0,1,1,0]，第二行的h为[0,2,2,0]。

2. 单调栈原理：

   • 栈中存储列索引，对应高度递增。例如，高度数组[2,2,0]的处理过程：
     1. 入栈1（h=2）、2（h=2）
     2. 遇到j=3（h=0），弹出栈顶2，计算面积(3-2)*2=2；弹出栈顶1，计算面积(3-1)*2=4
     3. 入栈1（h=0）
   • 面积计算逻辑：以弹出高度为高，宽度为当前列与弹出后栈顶列的差。

3. 边界处理：

   • a[n+1]=-1确保处理完所有列后栈中元素全部出栈，计算剩余高度的面积。
   • 初始化h数组为0，正确处理第一行的高度计算。

算法正确性证明

• 行压缩的有效性：将二维问题转化为一维直方图问题，每一行的高度数组正确反映了上方连续1的情况。
• 单调栈的高效性：每个元素入栈和出栈各一次，时间复杂度O(n)，总时间复杂度为O(mn)，适用于m,n≤2000的规模。
• 最大面积的正确性：对于每个可能的矩形，其高度由某一行的连续1高度决定，宽度由左右边界决定，单调栈确保找到所有可能的矩形。

示例解析

以输入数据的第二个测试用例为例：

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

• 各行的高度数组h：
  • 行0：[0,0,0,0]
  • 行1：[0,1,1,0]
  • 行2：[0,2,2,0]
  • 行3：[0,0,0,0]
• 处理行2的h=[0,2,2,0]：
  • a数组为[0,2,2,0,-1]（末尾加-1）
  • 单调栈处理：
    1. j=1（a=0）入栈
    2. j=2（a=2≥0）入栈
    3. j=3（a=2≥2）入栈
    4. j=4（a=0<2）：弹出j=3，面积(4-3)*2=2；弹出j=2，面积(4-2)*2=4；入栈2（a=0）
    5. j=5（a=-1<0）：弹出j=2，面积(5-1)*0=0
  • 最大面积为4，对应2×2的全1子矩阵。

复杂度分析

• 时间复杂度：O(mn)，其中m为行数，n为列数。每行处理时间O(n)，总时间O(mn)。
• 空间复杂度：O(n)，用于存储高度数组和单调栈。

总结

该算法通过行压缩和单调栈优化，高效解决了二维0-1矩阵的最大全1子矩阵问题。核心在于将二维问题转化为一维直方图问题，并利用单调栈快速计算每个直方图的最大面积，最终得到全局最大值。