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 - 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;
    }
}