求给定矩阵中最大H形图案的尺寸，允许最多1个o、无X字符

你之前的解法超时核心原因是枚举左右列的复杂度达到了O(n²)，叠加行处理的O(m)复杂度总规模会达到8e10量级，完全无法适配2000*2000的矩阵，我们可以换成按横梁行枚举+预处理+单调栈/分情况计算的思路，把总复杂度控制在O(mn)~O(mn logn)区间，完全可以满足题目要求。

第一步：预处理基础数据 #

首先我们遍历矩阵提前计算四个二维数组，所有计算规则里遇到X直接中断计数：

• up0[i][j]：从位置(i,j)向上（包含自身）连续无X、无o的最大长度
• down0[i][j]：从位置(i,j)向下（包含自身）连续无X、无o的最大长度
• left_valid[i][j]：第i行中j列左边第一个X/o的位置，没有则为-1
• right_valid[i][j]：第i行中j列右边第一个X/o的位置，没有则为n

同时对每个位置(i,j)计算高度参数 h[i][j] = min(up0[i][j]-1, down0[i][j]-1)，含义是如果(i,j)作为横梁与立柱的交点，上下可以各延伸的最大长度（要求≥1才能符合H形横梁不碰顶端底端的约束）。

第二步：分两种情况计算最大H尺寸 #

我们把问题拆成「无o的H」和「恰好含1个o的H」两种场景，分别计算最大值再取全局最大即可。

场景1：H形完全不含o #

按行枚举横梁所在行r，对于这一行所有连续无X、无o的区间，我们需要在区间内找两个列L<R，使得表达式4 * min(h[r][L], h[r][R]) + (R-L+1)最大。
这个问题可以用类似最大矩形的单调栈解法处理：维护一个单调递增的栈存储列索引和对应的h值，每弹出一个元素就计算以该元素h为公共高度的最大可能R-L，单次行处理复杂度O(n)，总复杂度O(mn)。

场景2：H形恰好含1个o #

我们直接枚举矩阵中每个o的位置(or, oc)作为H形里唯一的o，分三个子场景计算最大可能尺寸：

• 子场景2.1：o在左立柱
  先确定左立柱的上下边界：向上走直到碰到X/其他o得到顶部行topL，向下走直到碰到X/其他o得到底部行bottomL。横梁行r可以选(topL, bottomL)之间的任意行，横梁右边界最大为right_valid[r][oc]-1，在区间[oc+1, right_valid[r][oc]-1]中找最大的4*min(h[r][c2], min(r-topL, bottomL-r)) + (c2-oc+1)即可。
• 子场景2.2：o在右立柱
  逻辑和子场景2.1完全对称，反过来处理左边界即可。
• 子场景2.3：o在横梁上
  横梁行固定为or，左边界最大为left_valid[or][oc]+1，右边界最大为right_valid[or][oc]-1，在区间[left_valid[or][oc]+1, oc-1]和[oc+1, right_valid[or][oc]-1]中找c1<c2，最大化4*min(h[or][c1], h[or][c2]) + (c2-c1+1)即可。

上述子场景的区间查询可以通过对每行提前预处理线段树/ST表实现O(logn)查询，就算矩阵全是o，总操作量也只有4e7量级，完全可以在时限内跑完。

内容的提问来源于stack exchange，提问作者Dracullla