arrays - 具有最大乘积的行列或对角线

Question

我最近遇到了这个面试问题，Matrix largest product of n numbers in a row

我了解滚动乘法方法。我想知道如果我将问题限定为强制选择整行、整列或对角线，是否还有进一步的优化可能。

所以基本上现在的问题是，给定一个 NxM 矩阵，找到具有最大乘积的行或列或对角线。

是否有可能的 O(log n) 算法？

Answer 1

您必须至少查看每一行和每一列一次，因此您不能比 O(max(M, N)) 做得更好。为简单起见，许多人认为 M == N 并将其表示为 O(N)。

由于您还需要查看行/列中的每个元素，这使得它成为 O(M*N)。从本质上讲，这表明您需要在得出结果之前查看矩阵的每个元素。