2023-12-19 LeetCode每日一题(寻找峰值 II)
2023-12-31 22:41:45
2023-12-19每日一题
一、题目编号
1901. 寻找峰值 II
二、题目链接
三、题目描述
一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的 m x n 矩阵 mat ,其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。
你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
示例 1:
示例 2:
提示:
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 500
- 1 <= mat[i][j] <= 105
- 任意两个相邻元素均不相等.
四、解题代码
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int m = mat.size();
int low = 0, high = m - 1;
while (low <= high) {
int i = (low + high) / 2;
int j = max_element(mat[i].begin(), mat[i].end()) - mat[i].begin();
if (i - 1 >= 0 && mat[i][j] < mat[i - 1][j]) {
high = i - 1;
continue;
}
if (i + 1 < m && mat[i][j] < mat[i + 1][j]) {
low = i + 1;
continue;
}
return {i, j};
}
return {}; // impossible
}
};
五、解题思路
(1) 二分查找。
文章来源:https://blog.csdn.net/qq_56086076/article/details/135320080
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!