如何在二维数组中寻找相同角点构成的最大矩形？附实例求解

方法思路 #

要找四个顶点字符完全相同的矩形，核心是抓住矩形的上下两行中，存在两列的字符分别相等——因为这样的四个点（左上、右上、左下、右下）就构成了符合要求的矩形。这里给一个简单高效的实操步骤：

1. 遍历所有行对：把每一组上下行（i1在上，i2在下，i2 > i1）都过一遍，这是确定矩形高度的基础。
2. 筛选当前行对的匹配列：对每一列j，检查matrix[i1][j]和matrix[i2][j]是否相等，相等的话就记录下这个字符和列位置。
3. 找同字符的最大列跨度：对每个字符，收集所有匹配的列，然后在这些列里找跨度最大的两个列j1和j2（j2 > j1），这个跨度就是矩形的宽度。
4. 计算面积并更新最大值：用当前行对的高度（i2 - i1 + 1）乘以宽度，和之前记录的最大面积对比，保留更大的那个，同时记下对应的宽高。

这个方法对于中小规模的数组（比如题目里的7行10列）非常友好，逻辑清晰还不容易出错。

给定数组的求解过程 #

先把题目里的数组列出来方便对照（行号0-6，列号0-9）：

行0: ["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"]
行1: ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"]
行2: ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"]
行3: ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"]
行4: ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"]
行5: ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"]
行6: ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]

经过遍历所有行对后，找到的最大符合条件的矩形是：

• 高度：4（覆盖行1到行4，共4行）
• 宽度：8（覆盖列1到列8，共8列）

验证细节

这个矩形的四个角点字符都是A：

• 左上：行1列1 → A
• 右上：行1列8 → A
• 左下：行4列1 → A
• 右下：行4列8 → A

它的面积是4 × 8 = 32，是所有符合条件的矩形中最大的。其他候选比如行0到行3的B角点矩形（宽7，高4，面积28）、行3到行6的A角点矩形（宽7，高4，面积28），面积都小于这个值。

内容的提问来源于stack exchange，提问作者Jong Gyu Choi