对于具有整数值的 NxM 矩阵,找到区域 (x1,y1) (x2,y2) 的最小元素的最有效方法是什么,其中 0 <= x1<=x2 < M 和 0 <= y1 <= y2 < N
我们可以假设我们将多次查询不同的区域。
我想知道我们是否可以将范围最小查询方法扩展到这个问题。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
非常简单的解决方案可以是使用 RMQ(段树)最有效的解决方案,然后逐行或逐列地应用它。
最坏情况的复杂度是 min(N,M)*log(max(N,M))
但我仍然相信我们可以做得更好。