题解：超酷矩阵的最大子矩阵数量求解

算法标签

前缀和、单调栈、动态规划

问题分析

本题要求找出矩阵中最大的「超酷矩阵」子矩阵的元素数量。「超酷矩阵」的定义是其所有大小至少为 $(2 \times 2$) 的子矩阵都是「酷矩阵」，而「酷矩阵」需满足 $(A_{1,1} + A_{r,s} \le A_{1,s} + A_{r,1}$)（$(r,s>1$)）。

关键转化

将「酷矩阵」的条件转化为：对于子矩阵的左上角 $((i,j)$) 和右下角 $((i+1,j+1)$)，需满足 $(a[i][j] + a[i+1][j+1] \le a[i][j+1] + a[i+1][j]$)。我们可以预处理出一个二维数组 $(b$)，其中 $(b[i][j] = 1$) 表示以 $((i,j)$) 为左上角的 $(2 \times 2$) 子矩阵是酷矩阵，否则为 $(0$)。

核心算法思路

1. 预处理二维数组 (b) 并维护前缀和

• 计算 $(b[i][j]$) 时，若当前 $(2 \times 2$) 子矩阵是酷矩阵，进一步维护其在垂直方向的前缀和（即 $(b[i][j]$) 累加上方连续的酷矩阵数量），形成类似“直方图高度”的结构。

2. 单调栈求解最大矩形

• 对于每一行的 $(b$) 数组，将其视为直方图的高度数组，使用单调栈算法求解该直方图中最大矩形的面积。这里的矩形面积对应超酷矩阵的子矩阵大小（面积 $((h+1) \times (w+1)$)，其中 $(h$) 是垂直方向连续酷矩阵数，$(w$) 是水平方向连续酷矩阵数）。

3. 结果统计

遍历所有行的处理结果，取最大的子矩阵元素数量作为答案。

复杂度分析

• 预处理 $(b$) 数组的时间复杂度为 $(O(R \times S)$)。
• 对每一行使用单调栈处理的时间复杂度为 $(O(S)$)，总时间复杂度为 $(O(R \times S)$)。
• 整体时间复杂度为 $(O(R \times S)$)，可满足 $(R, S \le 10^3$) 的数据范围。

总结

本题通过将「超酷矩阵」的判定转化为二维数组的前缀和与单调栈求最大矩形问题，高效地解决了最大子矩阵的元素数量求解。核心在于利用动态规划维护垂直方向的连续酷矩阵数量，再结合单调栈在水平方向上的最优扩展，确保了算法的时间效率。