力扣1901、找出顶峰元素Ⅱ

1、二分法（124ms,95%;45.2MB,24%）

时间复杂度：O（nlog m）：m、n分别是矩阵的行数、列数

空间复杂度：O（1）

 1     //max_element(r,r+6)返回数组前6个元素中的最大值的地址
 2     //取值则为*max_element(r,r+6)
 3     //int(返回的地址-数组头地址)即为最大值在数组的序号
 4     vector<int> findPeakGrid(vectorint>>& mat) {
 5         //m,n分别是矩阵的行数、列数
 6         int m=mat.size();
 7         int n=mat[0].size();
 8 
 9         //num1,num2保存相邻三行的最上和最下两行的最大值
10         int num1=0,num2=0;
11         int left=0,right=m-1;
12         int mid=0;
13         while(left<=right){
14             mid=(left+right)/2;
15             num1=mid==0? -1:*max_element(mat[mid-1].begin(),mat[mid-1].end());
16             num2=mid==m-1? -1:*max_element(mat[mid+1].begin(),mat[mid+1].end());
17             //这里num3得到的是mid这行的最大值的地址
18             auto num3=max_element(mat[mid].begin(),mat[mid].end());
19             //如果中间那行的最大值比相邻两行的最大值还大即为目标值
20             if(*num3>=max(num1,num2))
21             return {mid,int(num3-mat[mid].begin())};
22             //每次只需用相邻三行比较，不断比较不断排除即可
23             else if(num1>=max(*num3,num2))
24             right=mid-1;
25             else
26             left=mid+1;
27         }
28         return {};
29     }