寻找峰值 II
难度:
标签:
题目描述
一个 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
// 使用Java Stream无法直接实现该算法，因为它需要在数组中执行二分查找和条件检查。
// 但我们可以用Java流来简化某些操作，比如查找最大值所在的行。
// 思路与上述Java解法类似。
import java.util.stream.IntStream;
public class Solution {
public int[] findPeakGrid(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
int maxRow = IntStream.range(0, m)
.boxed()
.max((i, j) -> Integer.compare(mat[i][mid], mat[j][mid]))
.get();
boolean isPeak = true;
if (mid > 0 && mat[maxRow][mid] < mat[maxRow][mid - 1]) {
right = mid - 1;
isPeak = false;
}
if (mid < n - 1 && mat[maxRow][mid] < mat[maxRow][mid + 1]) {
left = mid + 1;
isPeak = false;
}
if (isPeak) {
return new int[]{maxRow, mid};
}
}
return new int[]{-1, -1}; // 不会执行到这里
}
}
解释
方法:
该题解采用了二分搜索的策略，但不同于常规的一维二分搜索，它是对二维矩阵的行进行二分搜索。首先，选定中间行，然后在该行中找到最大值的列索引。接着，比较这个元素与其上下元素的大小。如果它小于上面的元素，则峰值在上半部分，调整高指针；如果它小于下面的元素，则峰值在下半部分，调整低指针。如果当前元素是当前所在列的最大值，并且比相邻的上下行元素都要大，则它就是一个峰值，返回其位置。
时间复杂度:
O(n log(m))
空间复杂度:
O(1)
代码细节讲解
🦆
在二分搜索中，选定中间行后，为什么总是选择该行中的最大值的列索引进行下一步比较？
▷🦆
如果中间行的最大值同样是列中的最高点，但其相邻格子有相同的值（不考虑题目中假设的不相同情况），这种搜索方法还有效吗？
▷🦆
题解中提到的边界检查，如`i - 1 >= 0`和`i + 1 < m`，是如何确保不会越界访问矩阵的？
▷🦆
题解假设整个矩阵周边环绕着一圈值为`-1`的格子，这种假设在实际代码实现中如何体现？
▷