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) 二分查找。