A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.
Given a /(0/)-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].
You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.
You must write an algorithm that runs in /(O(m /log(n))/) or /(O(n /log(m))/) time.
Solution
遍历每一行，然后对每一行进行二分，然后对于周边的四个都进行 /(check/):
点击查看代码
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int r=mat.size(), c=mat[0].size();
for(int i=0;i<r;i++){
int lft=0,rft=c-1;
while(lft<=rft){
int mid = (rft-lft)/2+lft;
int up = i-1>=0?mat[i-1][mid]:INT_MIN;
int dw = i+1<r?mat[i+1][mid]:INT_MIN;
int L = mid-1>=0?mat[i][mid-1]:INT_MIN;
int R = mid+1<c?mat[i][mid+1]:INT_MIN;
if(mat[i][mid]>up&&mat[i][mid]>dw&&mat[i][mid]>L&&mat[i][mid]>R)return {i,mid};
else if(L<R)lft=mid+1;
else rft=mid-1;
}
}
return {-1,-1};
}
};
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/289587.html