题目
一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的
m x n矩阵mat，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值mat[i][j]并 返回其位置[i,j]。你可以假设整个矩阵周边环绕着一圈值为
-1的格子。要求必须写出时间复杂度为
O(m log(n))或O(n log(m))的算法
解题思路
1.对行进行二分处理，再对获取当前行的最大值，比较上下位置；
代码展示
class Solution { public int[] findPeakGrid(int[][] mat) { int n = mat.length; //右边界减一，避免额外判断mid + 1是否超出范围,在这个范围内每次更新左边界，最后二分结果为m - 1 int left = 0; int right = n - 2; while (left <= right){ int mid = (left + right) / 2; int maxIndex = findMax(mat[mid]); if(mat[mid][maxIndex] > mat[mid + 1][maxIndex]){ //同上 right = mid - 1; } else { left = mid + 1; } } return new int[]{left,findMax(mat[left])}; } //寻找每行的最大值 private int findMax(int[] data){ int max = 0; for (int i = 1; i < data.length; i++){ if(data[i] > data[max]){ max = i; } } return max; } }
