文章目录
1. 题目
2. 解题
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]都是可接受的答案。
输入: 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 任意两个相邻元素均不相等.
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++
