1. 题目
一个 2D 网格中的 顶峰元素 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 顶峰元素 mat[i][j] 并 返回其位置 [i,j] 。
你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
示例 1:
输入: mat = [[1,4],[3,2]]
输出: [0,1]
解释: 3和4都是顶峰元素，所以[1,0]和[0,1]都是可接受的答案。
示例 2:
输入: mat = [[10,20,15],[21,30,14],[7,16,32]]
输出: [1,1]
解释: 30和32都是顶峰元素，所以[1,1]和[2,2]都是可接受的答案。
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 500
1 <= mat[i][j] <= 10^5
任意两个相邻元素均不相等.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-a-peak-element-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 对行进行二分查找，找到中行 mid， 及其上下两行，每行的最大值
- 如果 mid 行最大值 >= 相邻两行的，则找到了顶峰
- 否则，二分查找较大的一侧，顶峰元素肯定存在
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int l = 0, r = m-1, mid;
int u, v, w, idx;
vector<int> res;
while(l <= r)
{
mid = (l+r)>>1;
res = getmax(mat, mid, m, n);
u = res[0], idx = res[1];
res = getmax(mat, mid-1, m, n);
v = res[0];
res = getmax(mat, mid+1, m, n);
w = res[0];
if(u>=v && u>=w) return {mid, idx};
else if(v >= u)
r = mid-1;
else
l = mid+1;
}
return {-1, -1};
}
vector<int> getmax(vector<vector<int>>& mat, int r, int m, int n)
{
if(r < 0 || r >= m) return {-1, -1};
int maxv = -1, idx = -1;
for(int i = 0; i < n; ++i)
{
if(maxv < mat[r][i])
{
idx = i;
maxv = mat[r][i];
}
}
return {maxv, idx};
}
};
144 ms 45.2 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
