「ROI 2025 Day1」楼梯 题解

题目分析

我们需要在 $h \times w$ 的 $0/1$ 矩阵中找到一个最大的楼梯，满足：

1. 由若干连续行组成
2. 每行选中的格子是连续的 $1$
3. 每行的连续段长度非递减
4. 所有行的连续段左端点在同一列

关键观察

楼梯的几何性质：

• 如果固定左边界列 $L$，那么楼梯可以看作从某行开始，向右延伸不同长度的连续 $1$ 段
• 由于长度非递减，这实际上形成了一个"阶梯状"的区域
• 问题可以转化为：找到最大的阶梯状连通区域

算法思路

步骤1：预处理连续高度

对于每个格子 $(i,j)$，计算 up[i][j] 表示从该格子向上连续的 $1$ 的个数（包括自身）：

up[i][j] = (g[i][j] == '1') ? (up[i-1][j] + 1) : 0

这帮助我们快速判断某个位置向上能延伸多高。

步骤2：逐行处理

对每一行 $i$，我们考虑以该行为底的潜在楼梯。

步骤3：单调栈求右边界

对于当前行，up[i][j] 可以看作高度。我们要求的是：对于每个位置 $j$，找到右边第一个高度小于 up[i][j] 的位置 R[j]。

使用单调递增栈：

• 遍历每一列 $j$
• 当栈顶高度大于当前高度时，弹出栈顶元素，并记录其右边界为 $j$
• 将当前列入栈

步骤4：动态规划计算最大面积

从右向左遍历，计算 sum[j]：

sum[j] = sum[R[j]] + up[i][j] * (R[j] - j)

这里：

• up[i][j] 是高度
• (R[j] - j) 是宽度
• sum[R[j]] 是右边相邻区域的面积

sum[j] 表示从列 $j$ 开始向右能形成的最大楼梯面积。

步骤5：更新答案

对每个 sum[j] 取最大值作为最终答案。

算法正确性

这个解法巧妙地将问题转化为：

1. 对于每一行，计算向上连续 $1$ 的高度
2. 使用单调栈快速确定每个高度能向右延伸的范围
3. 通过动态规划累加可能的楼梯面积

由于楼梯要求长度非递减且左对齐，我们的解法正好满足：

• 左对齐：所有考虑的区域都从同一列开始向右延伸
• 长度非递减：通过高度约束和单调栈保证

复杂度分析

• 时间复杂度：$O(h \times w)$
  • 预处理连续高度：$O(h \times w)$
  • 每行的单调栈操作：$O(w)$
  • 动态规划计算：$O(w)$
• 空间复杂度：$O(h \times w)$

总结

本题的解法结合了：

• 预处理技巧：计算向上连续高度
• 单调栈：高效求边界
• 动态规划：累加最大面积

这种将二维问题转化为一维处理的思想，以及利用单调性优化计算的方法，在矩阵类问题中非常实用。