如何在由四个相同角落组成的2D数组中找到最大矩形？

Question

考虑一下这个数组：

[
  ["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]
]

我试图获取这个二维数组中具有最大面积的矩形的宽度和高度。答案应该是8 * 4 = 32（坐标为（1,1），（1,8），（4,1）和（4,8）），因为它具有相同角落“A”的最大面积。

- Jong Gyu Choi

---

我看不到你解决方案的矩形。 - Sebastian Speitel

矩形是什么意思？ - Satish Kumar

你应该解释一下A、B、C是颜色，并且你想要找到4个相同颜色的角落。 - RaphaMex

定义什么是“大”矩形：最大的面积还是周长？ - RaphaMex

抱歉，我想要最大的区域！ - Jong Gyu Choi

Answer 1

仅仅因为好笑:

var l = [ 
["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]];

var squares = [];
//for each position
for (var column=0; column< l[0].length; column++) 
   for (var row=0; row< l.length ; row++ ) 
    //look for all scuares from this position:
    for (var next_column = column+1; next_column < l[0].length; next_column++ )
        if ( l[row][next_column] == l[row][column] )
            for (var next_row = row+1; next_row < l.length; next_row++)
               //if it is a square
               if (l[next_row][column] == l[row][column] && 
                   l[next_row][next_column] == l[row][column]) 
                    //annotate square
                    squares.push( [ column, row, next_column, next_row  ] );

//get areas from squares
var area_l = squares.map(function(an_square) { 
    return (an_square[2]-an_square[0]+1)*(an_square[3]-an_square[1]+1);
  });

//search for big area
var max_area_index = area_l.indexOf(Math.max(  ...area_l  ));

//here it is
console.log( squares[max_area_index] );

Result: Array(4) [1, 1, 8, 4]

- dani herrera

---

仅考虑时间复杂度，这是O(m²n²)，对吧？我认为，一种方法是测试每个可能的矩形，从最大的开始，然后逐渐减小大小，可以得到一个O(n³)的解决方案。 - Sebastian Simon

嗨 @Xufox，谢谢你的评论 :) 我没有进行优化，只是一气呵成地写了出来。我喜欢你的问题。也许有人可以回答它，还有其他人可能会提出更好的优化或更优雅的方法。我不是JS开发者，这一点显而易见。 - dani herrera

其实，不用在意了...我在考虑每个可能的正方形。每个可能的矩形时间复杂度可能更差，但是从最大开始，然后逐渐减小尺寸的部分值得思考。 - Sebastian Simon

@Xufox，一个启发式规则可能是“不要搜索比已找到的最大矩形小的矩形”。 - dani herrera

@Xufox：我有一个类似这样的解决方案，正在等待OP解锁。 - RaphaMex

Answer 2

如果我们考虑以下事实：

1. 小矩形与大矩形拥有相同的概率具有4个相同的角落 2. 一个点可以是与任何其他点一样多的矩形的角落，无论其位置如何（N =（宽度-1）*（高度-1））

因此，我们确认了直觉算法：我们想首先寻找更大的矩形，这些矩形更有可能在边上而不是中心点上拥有角落，并且在找到它们时迅速停止。

方法1：按面积严格排序的矩形

该解决方案计算大矩形的形状以便查找它们。

困难的部分在于按面积排序的矩形并不像缩小正方形或圆形那么容易。面积为12的矩形可以具有[1,12]，[2,6]，[3,4]，[4,3]，[6,2]或[12,1]的形状，而面积为11的矩形只能具有[1,11]或[11,1]的形状。

function getGreatestRectangleStrict () {
    let hMax = tab.length - 1,
        wMax = tab[0].length - 1;
    // Search valid rectangle by decreasing area
    for (let area = (hMax+1)*(wMax+1); area >= 0; --area) {
        // Compute rectangle shapes that fit in tab with given area
        let kMax = Math.min(area, hMax + 1);
        for (let k = 1; k <= kMax ; ++k)
            if (area % k === 0) {
                let height = k - 1,
                    width = area / k - 1;
                if ( width <= wMax ) {
                    // New fitting shape found, test rectangles
                    for (let top = 0; top <= hMax - height; ++top)
                        for (let left = 0; left <= wMax - width; ++left) {
                            let bottom = top + height,
                                right = left + width,
                                a = tab[top][left];
                            if ( a === tab[bottom][left] &&
                                 a === tab[bottom][right] &&
                                 a === tab[top][right])
                                // Valid rectangle: stop search
                                return [top, left, bottom, right];
                        }
                }
            }
    }
}

它在小数组上表现非常好，但在大数组上表现不佳。我认为它需要一种启发式方法来快速查找形状，并在找到解决方案时停止。

第二种方法：混合高效搜索

此解决方案寻找矩形，并在找到一些大矩形时加速。

function getGreatestRectangleMixed () {
    let greatestArea = 0;
    let greatestRectangle = [];

    // Get horizontal pairs of corners of same color
    // and their vertical positions (y)
    let pairs = {};
    for (let k = 0; k < tab.length; ++k) {
        // Heuristic: alternately search top and bottom
        let y = ( !(k % 2) ? k/2 : tab.length - (k+1)/2);

        let line = tab[y];
        if ( line.length * Math.max(tab.length-y,y+1) < greatestArea )
            break; // Heuristic: height too small

        for (let i = 0; i < line.length - 1; ++i) {
            let color = line[i];
            for (let j = line.length - 1; j > i; --j) {
                if ( (j-i+1) * tab.length < greatestArea )
                    break; // Heuristic: width too small
                if (line[i] === line[j]) {
                    // Pair of corners found
                    let pairKey = i+" "+j;
                    let cornerPair = {
                        corners: [i,j],
                        width: j-i+1,
                        y: y
                    };
                    if (! (color in pairs) )
                        pairs[color] = {};
                    if (! (pairKey in pairs[color]) )
                        // New pair of corners found, keep only first one
                        pairs[color][pairKey] = cornerPair;
                    else {
                        // Rectangle found, check area
                        let isCurrentBottom = pairs[color][pairKey].y < cornerPair.y;
                        let top = (isCurrentBottom ? pairs[color][pairKey] : cornerPair);
                        let bottom = (isCurrentBottom ? cornerPair : pairs[color][pairKey]);
                        let area = top.width * (bottom.y - top.y + 1);
                        if (area > greatestArea) {
                            greatestArea = area;
                            greatestRectangle = [
                                [top.corners[0], top.y],
                                [top.corners[1], top.y],
                                [bottom.corners[0], bottom.y],
                                [bottom.corners[1], bottom.y]
                            ];
                        }
                    }
                }
            }
        }
    }

    return greatestRectangle;
}

这个解决方案在处理 OP 大小的矩形时比之前的解决方案略慢，但在处理更大的矩形时更加稳定。

- RaphaMex

---

方法二在 n 行和 m 列的情况下的时间复杂度是 O(n²m)，对吗？这个复杂度等同于将每对垂直角落点哈希到它们出现的列（n²），并且对于每个列（m），构建和/或查找哈希映射以找到匹配对，计算找到的矩形，并仅保留最大的矩形。我尝试过将行哈希到角落点、角落点哈希到行、行-行匹配哈希到列、矩形部分哈希到其他部分等许多不同的哈希方法，但我无法避免最终“检查每种可能性”，才能达到 O(nm) 的时间复杂度... - Sebastian Simon

我是说...除了预先解决每个数组并在常数时间内查找哈希之外。 - Sebastian Simon

@SebastianSimon：据我所记，我的第二个解决方案实现了一种记忆化的方式，即“我找到了一个这个面积的矩形，所以我停止寻找更小的矩形”。最坏情况就像你说的那样。但平均而言，它应该表现得更好。我相信我们可以做得更好，如果这个话题是活跃的，我可能会再花一些时间。 - RaphaMex

Answer 3

你可以先获取依赖数组中所有相同字母的位置，然后遍历数组以找到最右和最底的位置。接下来，检查另外两个点是否具有所需值。如果是，则将找到的矩形推送到临时结果集中。稍后对该数组进行排序或直接选择最大面积。

var array = [["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"], ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"], ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"], ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"], ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"], ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"], ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]],
    points = {},
    rectangles = [],
    count=0;

array.forEach((a, i) => a.forEach((b, j) => (points[b] = points[b] || []).push({ j, i })));

Object
    .keys(points)
    .forEach(k => {
        points[k].slice(0,-1).forEach((p, m) => {
            var n = points[k].length,
                q;

            while (n--) {
                q = points[k][n];
                if (p.i < q.i && p.j < q.j && k === array[p.i][q.j] && k === array[q.i][p.j]) {
                    rectangles.push({ key: k, top: p.i, left: p.j, bottom: q.i, right: q.j, size: (q.i - p.i + 1) * (q.j - p.j + 1) });
                }
            }
        });
    });

rectangles.sort((a, b) => b.size - a.size);

console.log(rectangles);

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz