交换列允许的情况下，找到由1组成的最大矩形

Question

我在以下网址找到这个问题和解决方案：http://www.geeksforgeeks.org/find-the-largest-rectangle-of-1s-with-swapping-of-columns-allowed/ 但是我无法理解所提供的解决方案。请问有人可以解释一下这个解决方案是如何工作的吗？

我已经尝试在纸上追踪和 stepping into 代码，但是无法理解： 1. 排序在其中扮演了什么角色。 2. 如何计算最终面积而不需要交换任何列，就像问题所要求的那样！

如果有帮助，将不胜感激！

- vinit

---

这个问题与编程无关 - 它是关于一个算法，无论你是写程序来实现它还是用纸和笔手动操作，都适用。我建议你去数学网站上提问。如果你在实现算法或理解建议的实现方面遇到问题，那么这就是可以提问的地方。 - undefined

Answer 1

1. 排序在其中扮演什么角色。
2. 如何在不交换任何列的情况下计算最终区域，正如问题所要求的那样！

排序 就是 列的交换。如果我们看步骤2下的第3行：

3 3 1 0 0

排序后的行对应于交换列，使得具有最大可能矩形的列首先放置，之后是允许第二高矩形的列，以此类推。因此，在该示例中，有两列可以组成高度为3的矩形。这使得面积为3*2=6。如果我们尝试让矩形变得更宽，则高度会降至1，因为在第三行上没有留下可以允许更高矩形的列。

编辑：避免不必要的排序

使用标准的O(n*log(n))排序算法可以获得良好的性能。

通过避免不必要的排序，可以减少所需的排序次数。以下建议不会减少O评级，但可以大大减少交换次数。

为了减少交换次数，我们需要尽早停止对行的排序。为了能够做到这一点，我建议使用快速排序，并始终首先对左分区（较高的数字）进行排序。每当枢轴乘以分区大小比我们到目前为止发现的最大矩形还要小时，我们就知道右分区（较低的数字）无法容纳最大矩形，因此我们可以跳过对右分区的排序。

例如：

假设到目前为止找到的最大矩形大小为6，下一行的排序如下：

1 3 0 3 0

我们以第一个元素1作为基准。基准乘以分区大小得到1 * 5 = 5，这小于或等于最大的发现的大小。这意味着我们可以跳过右侧的分区，因为它不能产生大于5的矩形。 3 3（继续对此分区进行排序） - 1 0 0（跳过此分区）

归并排序仅允许我们跳过最终合并的部分，这就是我选择快速排序的原因。

- Klas Lindbäck

---

谢谢，那真是帮了我大忙！ - undefined

如何将交换限制在最小范围内。@Klas Lindbäck - undefined

如果可以的话，请再详细解释一下 @KlasLindbäck 谢谢 - undefined

@Xax 我已经添加了一个例子。 - undefined

Answer 2

def rectangle(matrix):
    R = len(matrix)
    C = len(matrix[0])
    mtrx = []
    for i in range(R):
        row = []
        for j in range(C):
            #creating a matrix of 0
            row.append(0)
        mtrx.append(row)


    for i in range(C):
        #copy first row matrix
        mtrx[0][i] = matrix[0][i]
        #counting the consecutive ones
        for j in range(R):
            if matrix[j][i] == 0:
                mtrx[j][i] = 0
            else:
                mtrx[j][i] = mtrx[j-1][i]+1
    #sort the rows            
    for i in range(R):
        mtrx[i] = sorted(mtrx[i],reverse=True) 
    #Traverse the sorted matrix to find maximum area 
    max_area = 0
    for i in range(R):
        for j in range(C):
            current = (j+1) * mtrx[i][j]
            if current > max_area:
                max_area = current
    return max_area

matrix = [[0, 1, 0, 1, 0],
          [0, 1, 0, 1, 1],
          [1, 1, 0, 1, 0]]

- user7983445

---

虽然这段代码可能回答了问题，但最好解释如何解决问题并提供代码作为示例或参考。仅有代码的回答可能会令人困惑且缺乏上下文。 - undefined

这是给那些懂得如何阅读代码的人。我已经留下了注释，并且用Python实现了链接中给出的算法。 - user7983445