寻找峰值 II

方法一：二分查找

记 $m$ 和 $n$ 分别为矩阵的行数和列数。

题目要求我们寻找峰值，并且时间复杂度为 $O(m \times \log n)$ 或 $O(n \times \log m)$，那么我们可以考虑使用二分查找。

我们考虑第 $i$ 行的最大值，不妨将其下标记为 $j$。

如果 $mat[i][j] \gt mat[i + 1][j]$，那么第 $[0,..i]$ 行中必然存在一个峰值，我们只需要在第 $[0,..i]$ 行中找到最大值即可。同理，如果 $mat[i][j] \lt mat[i + 1][j]$，那么第 $[i + 1,..m - 1]$ 行中必然存在一个峰值，我们只需要在第 $[i + 1,..m - 1]$ 行中找到最大值即可。

为什么上述做法是对的？我们不妨用反证法来证明。

如果 $mat[i][j] \gt mat[i + 1][j]$，假设第 $[0,..i]$ 行中不存在峰值，那么 $mat[i][j]$ 不是峰值，而由于 $mat[i][j]$ 是第 $i$ 行的最大值，并且 $mat[i][j] \gt mat[i + 1][j]$，那么 $mat[i][j] \lt mat[i - 1][j]$。我们继续从第 $i - 1$ 行往上考虑，每一行的最大值都小于上一行的最大值。那么当遍历到 $i = 0$ 时，由于矩阵中的元素都是正整数，并且矩阵周边一圈的格子的值都为 $-1$。因此，在第 $0$ 行时，其最大值大于其所有相邻元素，那么第 $0$ 行的最大值就是峰值，与假设矛盾。因此，第 $[0,..i]$ 行中必然存在一个峰值。

对于 $mat[i][j] \lt mat[i + 1][j]$ 的情况，我们可以用类似的方法证明第 $[i + 1,..m - 1]$ 行中必然存在一个峰值。

因此，我们可以使用二分查找来寻找峰值。

我们二分查找矩阵的行，初始时查找的边界为 $l = 0$, $r = m - 1$。每一次，我们找到当前的中间行 $mid$，并找到该行的最大值下标 $j$。如果 $mat[mid][j] \gt mat[mid + 1][j]$，那么我们就在第 $[0,..mid]$ 行中寻找峰值，即更新 $r = mid$。否则，我们就在第 $[mid + 1,..m - 1]$ 行中寻找峰值，即更新 $l = mid + 1$。当 $l = r$ 时，我们就找到了峰值所在的位置 $[l, j_l]$。其中 $j_l$ 是第 $l$ 行的最大值下标。

时间复杂度 $O(n \times \log m)$，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。二分查找的时间复杂度为 $O(\log m)$，每次二分查找时，我们需要遍历第 $mid$ 行的所有元素，时间复杂度为 $O(n)$。空间复杂度 $O(1)$。