526互联

1901.寻找峰值

发布时间 2023-12-19 10:22:42作者: TTS-S

题目链接：1901.寻找峰值

题目：
一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。
你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法

示例1：
image

输入: mat = [[1,4],[3,2]]
输出: [0,1]
解释: 3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。

示例2：
image

输入: 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] <= 105
  • 任意两个相邻元素均不相等.

思路：
看完题目先看数据范围，所有数据都是正数，题目要求算法的时间复杂度为\(O(m log(n))或O(n log(m))\)，根据这个时间复杂度大致判断，我们可以对一行或者一列做遍历操作，但是选择这个行或列的时候应该需要复杂度为\(O(log)\)的算法，既然是寻找峰顶，我们可以想到二分来寻找，其时间复杂度为\(O(log)\)，那么我们现在需要想怎么做。
image

如图所示，对于每一个峰值来说，他相对于这一行的所有元素肯定是最大的。当我们找到这行最大的元素，我们判断他是不是峰值，如果他小于他下面的元素，那么他下面几行里一定包括一个峰顶。
同理，如果他小于他上面的元素，那么他上面的几行里一定包括一个峰顶。
若上诉两个情况都不成立，那么他就是峰顶。

代码：

class Solution {
    int get_j(vector<int> &a) {
        return max_element(a.begin(), a.end()) - a.begin();
    }

public:
    vector<int> findPeakGrid(vector<vector<int>> &mat) {
        int l = 0, r = mat.size() - 2;
        while (l <= r) {
            int i = l + (r - l) / 2;
            int j = get_j(mat[i]);
            if (mat[i][j] > mat[i + 1][j]) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
        return {l, get_j(mat[l])};
    }
};