1901. 寻找峰值 II (opens new window)

1.二维数组二分

根据题意，假设对于第i行已经求出了其最大值，那么只需要保证该行的最大值比上下两个位置的数大即可。有几种情况：

• 第i行最大值小于上方的数，那么可以在0 ~ i-1行搜寻结果，必定存在一个峰值。
• 第i行最大值小于下方的数，那么说明i+1 ~ m行肯定存在峰值。
• 上下两行都小于当前第i行最大值的结果，则直接返回当前最大值作为峰值。

本题二分的对象是跨行之间的最大值，最外层保证都是-1，因此这种二分方式必定有解。

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        //求最大值
        int low=0,high=mat.length-1;
        while(low<high){
            int mid=(low+high)>>1;
            int peakInx=0,peak=mat[mid][0];
            for(int i=0;i<mat[0].length;i++){
                if(mat[mid][i]>peak){
                    peak=mat[mid][i];
                    peakInx=i;
                }
            }
            if(mid-1>=0&&mat[mid-1][peakInx]>peak){
                high=mid;
                continue;
            }
            else if(mid+1<mat.length&&mat[mid+1][peakInx]>peak){
                low=mid+1;
                continue;
            }
            else{
                low=mid;
                break;
            }
        }
        int peakInx=0,peak=mat[low][0];
        for(int i=0;i<mat[0].length;i++){
            if(mat[low][i]>peak){
                peak=mat[low][i];
                peakInx=i;
            }
        }
        return new int[]{low,peakInx};
    }
}