在矩阵B中寻找最大元素，比O(n)更好？实践技术面试

Question

假设我们有一个矩阵B，大小为n×n，具有不同的整数元素。如果局部最大值大于它的所有邻居(也是对角线)，则存在局部最大值。假设B恰好有一个局部最大值，B的每一列都有一个局部最大值。证明了我们可以在比O(n)更好的情况下找到B的局部最大值。

我的尝试:我想象“假设B恰好有一个局部最大值”这句话是为了告诉我一些关于定位(排序？)元素，但我似乎能抓住它。好于O(n)是一个约束的事实告诉我使用分而治之( O(logn*logn) ?)是一种很好的方法，但我不确定要递归到什么地方。

Answer 1

我认为它可以在O(n)中完成。

看问题说他们只有1个全局最大值(即整个矩阵的1个局部最大值)，并且每列都有一个局部最大值。

1. 从第一列开始，找出局部最大值(比如在(i，j))。检查它是否为全局最大值。
2. 如果不是全局最大值，则其必须是相邻单元格中下一列的局部最大值((i，j+1)，(i-1，j+1) & (i+1，j+1)，如果这些单元格存在)，它必须大于当前的局部最大值。

现在重复这些步骤，在每个步骤中，您将在固定时间内找到下一列的局部最大值(您只需要比较步骤2中指定的三个单元格)和最大值no。需要搜索的列数=n(最坏情况下的全局最大值位于最后一列)。

因此，总复杂度为O(n)。