我试图为下面的问题发明一种有效的算法，但我认为我失败了。我得到了一个板 n * n，里面有不同的数字和一个整数 k （k <= n）。 我必须找到一个包含在棋盘中的正方形 k * k，其中不同数字的数量最大。对于这些示例：
n=4 k=3
10 9 8 1
7 6 5 7
5 3 0 2
3 4 1 3
n=4 k=2
1 2 1 2
2 1 2 1
1 2 1 2
2 1 3 4
答案如下：
9 8 1
6 5 7
3 0 2
1 2
3 4
我对这个问题的解决方案（C++年）是基于选择左上角的第一个方形k*k，创建一个将数字（键）与其出现频率（值）联系起来的地图。然后，我通过删除地图中正方形的第一列并添加下一列来进一步移动正方形一列。当我到达右侧时，我向下移动一排，向左移动到边界。然后下一步，直接到边境。依此类推，直到我走到最后。答案基于特定时刻地图的最大大小。我认为这个解决方案发明得很差（但可能仍然比蛮力更好），我感谢任何建议。这个问题可以以某种方式简化为修改后的最大矩形问题吗？（ http://www.drdobbs.com/database/184410529 ）
根据丹尼尔的建议编辑（其他细节）
一开始，我的算法分析第一个 k*k 平方，即：10 9 8 |7 6 5 |5 3 0.分析每个元素时，它会将正确的数据写入地图。所以首先我有一对 （10 -> 1）（数字 10 出现一次），然后我加上 （9 -> 1）、（8 -> 1）、（7 -> 1）、（6 -> 1）、（5 -> 1）。然后我遇到下一个 5，所以我将其出现次数更改为 2 （5 -> 2）。最后我加上 （3 -> 1）、（0 -> 1）。实际上我的地图包含 8 个元素（因为如上所述，5 个元素出现了两次）。我记得这个正方形的坐标和地图的大小。我将我的 k*k 正方形向右移动一列。因此，我减少了地图中第一列元素的外观。所以我删除了对 （10 -> 1） 和 （7 -> 1），并将 （5 -> 2） 更改为 （5 -> 1）。我添加最后一列：（1 -> 1）、（7 -> 1）和（2 -> 1）（因为所有数字都是新的）。现在我注意到地图的大小比以前大（9>8），所以我将当前坐标保存在旧坐标上。实际上我在这里结束了我的算法（我的附加条件：if（map.size（） == k*k） end; ），但否则我会"走"一行，而不是向左直到边界，这样我就完成了对所有可能的 k*k 平方的分析。
实际上，我正在寻找更好的时间消耗解决方案，因为我的解决方案被测试系统拒绝（我超过了时间限制）。我认为它比蛮力更好，因为我不会逐个分析每个方格，但我可能是错的。无论如何，它仍然不够好。
我可以附加C++代码，以防对您来说更容易，但我怀疑它会有所帮助。我只是在寻找算法建议。
你的算法听起来不错，时间复杂度O(n * n * k * log k)，内存O(k * k)。如果您知道示例中的值是小整数，则可以通过将映射替换为数组来摆脱log k。否则，实现算法的代码中可能存在效率低下的问题。尝试根据n和k的变化来计时代码，以查看时间是否按预期增长。
作为另一个可能的方向，您可以尝试动态编程风格的解决方案。定义函数f(x, y, a, b)以计算锚定在 (x, y) 的 a x b矩形中的唯一值集（可能是位图）。那么问题是找到|f(x, y, k, k)|的最大值。 f(x, y, a, b)计算为 4 个或更多较小矩形集的并集，其维度约为 a/2 x b/2。如果缓存了较小的矩形集，则不必继续重新计算它们。缓存会占用大量内存，但您可以通过安排分解以使用 2 种大小的幂来限制它。例如
f(x, y, 21, 21) = f(x, y, 16, 16)
union f(x + 16, y, 4, 16)
union f(x + 20, y, 1, 16)
union f(x, y + 16, 16, 4)
union f(x, y + 20, 16, 1)
union f(x + 16, y + 16, 4, 4)
union f(x + 20, y + 16, 1, 4)
union f(x + 16, y + 20, 4, 1)
union f(x + 20, y + 20, 1, 1)
我认为这种方法更像 O（n * n * log k * log k），因此只会在 k 的大值（例如大于 1000）时获得回报。