algorithm - 如何找到矩阵区域中的最小或最大元素？

Question

对于具有整数值的 NxM 矩阵，找到区域 (x1,y1) (x2,y2) 的最小元素的最有效方法是什么，其中 0 <= x1<=x2 < M 且 0 <= y1 <= y2

我们可以假设我们将多次查询不同的区域。

我想知道我们是否可以将范围最小查询方法扩展到这个问题。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

非常简单的解决方案可以是使用最有效的 RMQ 解决方案 (Segment Tree)，然后按行或按列应用它。

最坏情况下的复杂度为 min(N,M)*log(max(N,M))

但我仍然相信我们可以做得更好。

Answer 1

这取决于您所说的“最有效的方式”是什么意思。可以最大限度地减少查询时间本身、预处理时间或内存需求。

如果只想尽量减少查询时间，“最有效的方法”是预先计算所有可能的区域。然后通过返回一些预先计算的值来处理每个查询。查询时间为 O(1)。内存和预处理时间都很大:O((NM)²).

更实用的是使用Sparse Table algorithm来自OP中提到的页面。该算法准备了一个包含所有二次方长度区间的表，并使用一对这些区间来处理任何范围最小查询。查询时间为 O(1)。内存和预处理时间为 O(N log N)。并且该算法可以很容易地扩展到二维情况。

只需准备一个包含所有长度的二次方和高度的二次方的矩形的表格，并使用其中的四个矩形来处理任何范围最小查询。对于这些矩形中的每一个，结果只是至少四个最小值。查询时间为 O(1)。内存和预处理时间为O(NM*log(N)*log(M))。

本文:"Two-Dimensional Range Minimum Queries" by Amihood Amir, Johannes Fischer, and Moshe Lewenstein建议如何将该算法的内存需求和预处理时间减少到几乎 O(MN)。

本文:"Data Structures for Range Minimum Queries in Multidimensional Arrays" by Hao Yuan and Mikhail J. Atallah给出了具有 O(1) 查询时间和 O(NM) 内存和预处理时间的不同算法。