来源：AT_abc311_g [ABC311G] One More Grid Task
难度 : 提高+/省选−
一：思路
算法的核心思想：把二维问题转化为一维问题
1.枚举矩阵的上边界 u 和 下边界 d，锁定一个纵向的条带；
2.对这个条带，按列压缩：
·计算每一列的元素和 sum[i]
·计算每一列的元素最小值 mi[i]
3. 此时二维矩阵被压缩成一维柱状图（横轴是列，柱子值是sum[i]，柱子最小高度是mi[i]）；
4.用单调栈求解这个一维柱状图的最大权值：最小值 × 区间和；
5.遍历所有上下边界，记录全局最大值。
二：代码解析
1. 输入与初始化
· 读取矩阵的行数n、列数m；
· 存储矩阵maze（下标从 1 开始，避免边界判断麻烦）；
· 初始化答案ans=0（用long long防止溢出）。
2.枚举矩阵的上边界 u
·u：矩阵的上边界行号；
·重置三个关键数组（每次上边界改变，需要重新计算）：
___sum[i]：第i列，从u到当前行的元素和；
___mi[i]：第i列，从u到当前行的元素最小值（初始化为无穷大）；
___pre[i]：sum数组的前缀和，快速计算区间和。
3. 枚举矩阵的下边界 d，压缩列数据
· d：矩阵的下边界行号（从u开始向下扩展）；
· 核心压缩操作：
____sum[i] += maze[d][i]：累加当前行，得到列[u,d]的总和；
____mi[i] = min(mi[i], maze[d][i])：更新列[u,d]的最小值；
· 前缀和pre：pre[r] - pre[l] = sum[l+1] + sum[l+2] + ... + sum[r]，O (1) 求区间和。
4. 单调栈求左右边界（最核心！）
作用：
· left[i]：i左边第一个小于 mi[i] 的列下标；
· right[i]：i右边第一个小于 mi[i] 的列下标；
意义：
以 mi[i] 作为最小值的最大连续区间是：[left[i] + 1 , right[i] - 1]
5. 计算答案，更新全局最大值
公式含义：
___mi[i] = 子矩阵的最小值
___pre[right[i]-1] - pre[left[i]] = 子矩阵的元素和
___乘积 = 当前子矩阵的权值
遍历所有列，更新全局最大答案ans。
6. 输出结果
总结：
1.二维转一维
枚举上下边界，将二维矩阵压缩为一维数组，是处理矩阵子问题的通用技巧。
2.单调栈
O (m) 时间求出每个元素作为最小值的最大作用区间，是解决柱状图最大矩形的最优算法。
3**.前缀和**
快速计算区间和，避免重复遍历，优化时间复杂度。
4.时间复杂度
O (n²m)：枚举上下边界 O (n²) + 单调栈 O (m)，适合中等规模矩阵。
完整代码：
团队招人哦，链接：https://www.acgo.cn/application/1811737919264829440
