建网站赚钱方法,如何用wordpress做企业,it外包wordpress模板,wordpress cart插件文章目录1. 题目2. 解题1. 题目
一个 2D 网格中的 顶峰元素 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的 m x n 矩阵 mat #xff0c;其中任意两个相邻格子的值都 不相同 。找出 任意一个 顶峰元素 mat[i][j] 并 返回其位置 [i,j] 。 …
文章目录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]都是可接受的答案。示例 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:vectorint findPeakGrid(vectorvectorint mat) {int m mat.size(), n mat[0].size();int l 0, r m-1, mid;int u, v, w, idx;vectorint res;while(l r){mid (lr)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, mid1, m, n);w res[0];if(uv uw) return {mid, idx};else if(v u)r mid-1;elsel mid1;}return {-1, -1};}vectorint getmax(vectorvectorint 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阿明一起加油、一起学习进步
