具有相同数字的最大矩形子矩阵

Question

我正在尝试设计一种动态规划算法，以查找由相同数字组成的矩阵中最大的子矩阵：

例如：

{5 5 8}
{5 5 7}
{3 4 1}

答案：由于矩阵的存在，有4个元素。

   5 5 
   5 5   

- TimeToCodeTheRoad

---

连续子矩阵，或者您允许重新排序？ - RBarryYoung

“largest” 的意思是 “元素数量最多” 吗？你只需要一个解决方案吗？这个方案是哪一个并不重要吗？ - Jeffrey Sax

@PengOne：我尝试了动态规划，但是它没有起作用。也许我定义的子问题有误。我定义了一个称为S[i][j]的数组，它存储具有所有元素等于M[i][j]的最大子矩阵的长度，然而，经过数小时的思考，我意识到它违反了最优子结构性质。 - TimeToCodeTheRoad

嗨！我认为动态规划在这里不是一个合适的工具（除非这是一份作业）。我发布了一个在O(n)中运行的解决方案，显然这是最好的可能性。我认为动态规划在这里会很笨拙（只是因为你提到的分解）。 - Tomas

重复的问题 https://dev59.com/J3E95IYBdhLWcg3wDpmg - tommy.carstensen

Answer 1

这是我已经在这里（和这里，修改版）回答过的问题。在这两种情况下，算法都应用于二进制情况（零和一），但对于任意数字的修改很容易（但抱歉，我保留了二进制版本的图像）。您可以通过两次遍历的线性O(n)时间算法非常高效地完成此操作 - 其中n为元素数量。然而，这不是动态规划 - 我认为在这里使用动态规划会很笨拙和低效，因为问题分解存在困难，正如OP所提到的 - 除非它是作业 - 但在那种情况下，您可以尝试通过这个算法来给人留下印象 :-)，因为显然没有比O(n)更快的解决方案。

算法（图片描述二进制情况）：

假设您想要找到最大的自由矩形（白色元素）。

以下是两遍线性O(n)时间复杂度算法（n为元素数量）：

1）第一遍，按列从下到上进行，对于每个元素，标记该元素之前连续可用的元素数量：

重复，直到：

这些图片描述了二进制情况。对于任意数字的情况，您需要持有两个矩阵——第一个是原始数字，第二个是填充在上图中的辅助数字。您需要检查原始矩阵，如果找到一个与前一个不同的数字，您只需从1开始在辅助矩阵中重新编号。

2) 在第二次遍历中，您按行遍历，持有潜在矩形的数据结构，即包含当前位置的矩形在顶部边缘的矩形。请参见以下图片（当前位置为红色，3个潜在矩形：紫色高度为1，绿色高度为2，黄色高度为3）：

对于每个矩形，我们保留其高度 k 和其左侧边缘。换句话说，我们跟踪连续数字的总和，这些数字大于或等于 k（即高度为 k 的潜在矩形）。这种数据结构可以由带有双向链接的占用项的数组表示，并且数组大小将受矩阵高度的限制。

第二遍扫描的伪代码（非二进制版本，具有任意数字）：

var m[] // original matrix
var aux[] // auxiliary matrix filled in the 1st pass
var rect[] // array of potential rectangles, indexed by their height
           // the occupied items are also linked in double linked list, 
           // ordered by height

foreach row = 1..N // go by rows
    foreach col = 1..M
        if (col > 1 AND m[row, col] != m[row, col - 1]) // new number
            close_potential_rectangles_higher_than(0);  // close all rectangles

        height = aux[row, col] // maximal height possible at current position

        if (!rect[height]) { // rectangle with height does not exist
            create rect[height]    // open new rectangle
            if (rect[height].next) // rectangle with nearest higher height
                                   // if it exists, start from its left edge
                rect[height].left_col = rect[height].next.left_col
            else
                rect[height].left_col = col; 
        }

        close_potential_rectangles_higher_than(height)
    end for // end row
    close_potential_rectangles_higher_than(0);
        // end of row -> close all rect., supposing col is M+1 now!

end for // end matrix

关闭矩形的函数：

function close_potential_rectangles_higher_than(height)
    close_r = rectangle with highest height (last item in dll)
    while (close_r.height > height) { // higher? close it
        area = close_r.height * (col - close_r.left_col)
        if (area > max_area) { // we have maximal rectangle!
            max_area = area
            max_topleft = [row, close_r.left_col]
            max_bottomright = [row + height - 1, col - 1]
        }
        close_r = close_r.prev
        // remove the rectangle close_r from the double linked list
    }
end function

这样你也可以得到所有的最大矩形。因此最终你会得到：

而复杂度将会是什么呢？你可以看到函数close_potential_rectangles_higher_than每个关闭的矩形都是O(1)。因为对于每个场地，我们最多创建一个潜在的矩形，在特定行中存在的潜在矩形总数永远不会超过该行的长度。因此，这个函数的复杂度是摊销的O(1)！整个复杂度是O(n)，其中n是矩阵元素的数量。

- Tomas

---

谢谢你的更新！我仍在努力理解时间复杂度部分。我想请求你是否可以提供一些代码，因为即使在之前的帖子中也没有提供。因此，这将非常有帮助。我只是要求第二遍的代码。正如你可能已经意识到的那样，你的解决方案是最有效的，因此我真的很感兴趣第二部分的代码。 - TimeToCodeTheRoad

很抱歉，我需要一点帮助理解第二部分。你在2.1中所说的最近更高矩形是什么意思？是指高度大于k的结构中的第一个矩形吗？你所说的潜在矩形是指开放矩形吗？如果你能提供一些粗略的伪代码，我会非常感激。这个算法有一个名字吗？我正在尝试解决类似的问题。 - salvador p

亲爱的@TimeToCodeTheRoad和user451963，请查看我的更新帖子 - 我已经添加了伪代码，复杂性解释和一个方案来解释我所谓的潜在矩形！ - Tomas

@user451963，感谢您的评论，是的，我所说的潜在矩形指的是开放式矩形！这个算法没有名称，我只记得它是我们在大学一年级编程课上做过的一个美妙练习 :-) 我们的老师很有启发性 :-) - Tomas

@TMS 这个问题是否与这个类似？如果是的话，你能告诉我如何绘制第二个矩阵吗？ - Khamidulla

Answer 2

一种动态解决方案：

定义一个新的矩阵A，它将在A[i,j]中存储两个值：以i,j为左上角的最大子矩阵的宽度和高度，从右下角开始按行自下而上填充此矩阵。 你将会发现四种情况：

情况1：原始矩阵中右侧或底部邻居元素均不等于当前元素，即：M[i,j] != M[i+1,j] 且 M[i,j] != M[i,j+1]，其中M是原始矩阵，在这种情况下，A[i,j]的值为1x1

情况2：右侧的邻居元素等于当前元素，但底部的元素不同，A[i,j].width的值为A[i+1,j].width+1，A[i,j].height=1

情况3：底部的邻居元素相等，但右侧的元素不同，A[i,j].width=1, A[i,j].height=A[i,j+1].height+1

情况4：两个邻居均相等：A[i,j].width = min(A[i+1,j].width+1,A[i,j+1].width)和A[i,j].height = min(A[i,j+1]+1,A[i+1,j])

具有左上角在i,j处的最大矩阵的大小为A[i,j].width*A[i,j].height，因此可以在计算A[i,j]时更新找到的最大值。

底行和最右侧列元素被视为其底部和右侧邻居不同

在您的示例中，生成的矩阵A如下：

{2:2 1:2 1:1}
{2:1 1:1 1:1}
{1:1 1:1 1:1}

“w:h”代表“宽:高”，用于指定元素的宽度和高度。

- Orlando William

---

每个矩阵单元只需要进行几个O(1)操作，因此时间复杂度为O(n)，其中n是矩阵的大小。 - Orlando William

“few” 是否确定是一个常量？ - Tomas

@OrlandoWilliam，请问您能解释一下第4个案例更新背后的逻辑吗？我的意思是，为什么要取最小值？ - TimeToCodeTheRoad

@OrlandoWilliam：我认为该算法无法处理以下情况： {A 0 0}, {A A A}, {A A A}, {A B B}， 因为对于最上面的A，算法会发现底部数字相同，但右侧数字不同，因此高度为3，宽度为1，但最优解应该是高度为4，宽度为1。你怎么看？ - TimeToCodeTheRoad

@OrlandoWilliam：嘿，你同意算法有点问题吗？原因是如果人们稍后看到这篇帖子，他们将能够理解它？ - TimeToCodeTheRoad

Answer 3

这个问题是一个重复。我已经尝试标记它为重复。这里有一个Python解决方案，它还返回最大矩形子矩阵的位置和形状：

#!/usr/bin/env python3

import numpy

s = '''5 5 8
5 5 7
3 4 1'''

nrows = 3
ncols = 3
skip_not = 5
area_max = (0, [])

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if not a[r][c] == skip_not:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            area = (dh+1)*minw
            if area > area_max[0]:
                area_max = (area, [(r, c, dh+1, minw)])

print('area', area_max[0])
for t in area_max[1]:
    print('coord and shape', t)

输出：

area 4
coord and shape (1, 1, 2, 2)

- tommy.carstensen

Answer 4

对上面答案的修改：

定义一个新矩阵A，它将在A [i，j]中存储两个值：左上角为i，j的最大子矩阵的宽度和高度，从右下角开始按行自下而上填充此矩阵。您会发现四种情况：

情况1：原始矩阵中的右侧或底部邻居元素都不等于当前元素，即：M [i，j]！= M [i + 1，j]且M [i，j]！= M [i，j + 1]，在这种情况下，A [i，j]的值为1x1

情况2：右侧的邻居元素与当前元素相等，但底部的邻居元素不同，则A [i，j] .width的值为A [i + 1，j] .width + 1，A [i，j] .height = 1

情况3：底部的邻居元素相等，但右侧的邻居元素不同，则A [i，j] .width = 1，A [i，j] .height = A [i，j + 1] .height + 1

情况4：两个邻居都相等： 考虑三个矩形： 1. A [i，j] .width = A [i，j + 1] .width + 1; A [i，j] .height = 1;

1. A[i,j].height=A[i+1,j].height+1; a[i,j].width=1;

2. A[i,j].width=min(A[i+1,j].width+1,A[i,j+1].width)且A[i,j].height=min(A[i,j+1]+1,A[i+1,j])

在上述三种情况中面积最大的矩阵将被视为表示该位置的矩形。

左上角坐标为 i，j 的最大矩阵大小是 A[i,j].width*A[i,j].height，因此在计算 A[i,j] 时可以更新找到的最大值。

底部行和最右列的元素被处理为其底部和右侧的邻居不同。

- Tanu Saxena