algorithm - 在允许交换列的情况下找到最大的 1 矩形

Question

我在以下位置遇到了这个问题和解决方案:http://www.geeksforgeeks.org/find-the-largest-rectangle-of-1s-with-swapping-of-columns-allowed/

但我无法理解所提供的解决方案。有人可以解释一下该解决方案的工作原理吗？

我已经尝试在纸上进行跟踪并进入代码，但无法理解:1、排序起到什么作用。2. 如何在不按问题要求交换任何列的情况下计算最终面积!

非常感谢任何帮助!

Answer 1

1. What role the sorting plays.
2. How the final area is being calculated without swapping any column as the question demands !

排序是列的交换。如果我们查看第 2 步下的第 3 行:

3 3 1 0 0

排序后的行对应于交换列，以便首先放置具有最高矩形的列，然后是允许第二高矩形的列，依此类推。因此，在示例中，有 2 列可以形成高度为 3 的矩形。这使得面积为 3*2=6。如果我们尝试使矩形更宽，则高度会下降到 1，因为没有剩余的列允许在第 3 行使用更高的矩形。

编辑:避免不必要的排序

使用标准的 O(n*log(n)) 排序算法为我们提供了良好的性能。

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

为了减少交换次数，我们需要尽快中止对行的排序。为了能够做到这一点，我建议使用快速排序并始终首先对左侧分区(较大的数字)进行排序。每当主元乘以分区大小小于我们迄今为止找到的最大矩形时，我们就知道正确的分区(较小的数字)不能容纳最大的矩形，因此我们可以跳过对正确的分区进行排序。

例子:

假设目前找到的最大矩形的大小为 6 并且要排序的下一行如下所示:

1 3 0 3 0

我们将第一个元素 1 作为基准。主元乘以分区大小为 1 * 5 = 5，小于或等于找到的最大大小。这意味着我们可以跳过正确的分区，因为它不能产生大于 5 的矩形。

3 3(继续排序这个分区)- 1 0 0(跳过这个分区)

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