1901. 寻找峰值 II --力扣 --JAVA

题目

一个 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 - 1int 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;}
}