难度: Medium
一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。
你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
示例 1:
输入: mat = [[1,4],[3,2]] 输出: [0,1] 解释: 3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。
示例 2:
输入: mat = [[10,20,15],[21,30,14],[7,16,32]] 输出: [1,1] 解释: 30 和 32 都是峰值，所以[1,1]和[2,2]都是可接受的答案。
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 5001 <= mat[i][j] <= 105运行时间: 36 ms
内存: 43.8 MB
class Solution:
def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
m = len(mat)
low, high = 0, m - 1
while low <= high:
i = (low + high) // 2
j = mat[i].index(max(mat[i]))
if i - 1 >= 0 and mat[i][j] < mat[i - 1][j]:
high = i - 1
continue
if i + 1 < m and mat[i][j] < mat[i + 1][j]:
low = i + 1
continue
return [i, j]
return None
该题解采用了二分搜索的策略，但不同于常规的一维二分搜索，它是对二维矩阵的行进行二分搜索。首先，选定中间行，然后在该行中找到最大值的列索引。接着，比较这个元素与其上下元素的大小。如果它小于上面的元素，则峰值在上半部分，调整高指针；如果它小于下面的元素，则峰值在下半部分，调整低指针。如果当前元素是当前所在列的最大值，并且比相邻的上下行元素都要大，则它就是一个峰值，返回其位置。
时间复杂度: O(n log(m))
空间复杂度: O(1)
class Solution:
def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
m = len(mat) # 矩阵的行数
low, high = 0, m - 1 # 二分搜索的起始和终止行
while low <= high:
i = (low + high) // 2 # 计算中间行的索引
j = mat[i].index(max(mat[i])) # 找到中间行最大值的列索引
# 检查是否小于上一行同列的元素
if i - 1 >= 0 and mat[i][j] < mat[i - 1][j]:
high = i - 1 # 调整高指针
continue
# 检查是否小于下一行同列的元素
if i + 1 < m and mat[i][j] < mat[i + 1][j]:
low = i + 1 # 调整低指针
continue
# 当前元素是一个峰值，返回其位置
return [i, j]
return None # 理论上不会执行到这里，因为题目保证至少存在一个峰值
在二维矩阵中，选定中间行后选择该行中的最大值的列索引进行下一步比较是因为这个最大值有可能是一个局部峰值。从这个最大值出发，只需要比较其上下的元素即可快速确定是否存在更高的值，从而决定搜索的方向。这种方法有效减少了比较的范围和复杂度，使得算法更加高效。
在题目假设中，矩阵的所有元素都是不相同的，这使得每次比较都能明确地决定搜索方向。如果假设不成立，即存在相同的值，则可能无法通过当前的比较确定明确的搜索方向，因为可能存在多个相同的局部最大值。在这种情况下，算法可能需要更多的逻辑来处理这种特殊情况，或者可能无法保证总是找到峰值。
这些边界检查确保在比较当前元素与其上下行元素时，不会访问矩阵的外部。`i - 1 >= 0` 确保当前行不是第一行，从而可以安全地访问上一行；`i + 1 < m` 确保当前行不是最后一行，从而可以安全地访问下一行。这些检查是防止数组越界异常的重要保护措施。
题解中的这种假设主要是为了简化边界条件的处理。在实际代码实现中，我们并没有真正添加这样一圈值为`-1`的格子，而是通过边界检查（如前述的`i - 1 >= 0`和`i + 1 < m`）来模拟这种情况。这样，任何尝试访问矩阵边界之外的元素的操作都会被这些边界检查所阻止，从而在逻辑上等同于周边有`-1`的格子。