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：（图片源自力扣）

输入: 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]都是可接受的答案。

解法一：
??这种解法是一种取巧，既然存在峰值，那么我们只要找到最大的那个值，他就一定是峰值。所以我们只需要遍历完找出最大值即可。

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        
        int max = 0;
        int max_i = 0, max_j = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j <= n / 2; j++)
            {
                if(mat[i][j] > max)
                {
                    max_i = i;
                    max_j = j;
                    max = mat[i][j];
                }
                if(mat[i][n - 1 - j] > max)
                {
                    max_i = i;
                    max_j = n - 1 - j;
                    max = mat[i][n - 1 - j];
                }
            }
        }
        return {max_i, max_j};
    }
};

解法二：
??根据峰值出现的位置不同以及矩阵本身的情况，进行一个分类。
??情况一：矩阵只有一个数，那这个数本身就是一个峰值，直接返回。
??情况二：是只有一列或者一行。这种情况下对峰值可能出现的位置进行分类，一个是是出现在头部或者尾部，另一个就是除开头部尾部之外的位置。出现在头部或者尾部就只需要与它相邻的那一个值进行比较久可以判断是否是峰值，另一个情况则是需要与左右的值进行比较，才能判断是否是峰值。
??情况三：是一个正常矩阵，这时把矩阵进行拆分。分为四个角、四条边和中心部分。峰值在四个角时需要在上下、左右的排列组合中进行一个比较来判断是否是峰值。峰值在四条边时，则是与左右的值加上一个值进行比较。峰值在中心部分，则需要与上下左右四个值都进行一次比较才能判断是否是峰值。

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();

        int i = 0, j = 0;
        if(m == 1 && n == 1)
            return {0, 0};

        if(m < 2 || n < 2)
        {
            if(mat[i][j] > mat[i][j + 1])   return {i, j};
            if(mat[i][n - 1] > mat[i][n - 1 - 1]) return {i, n - 1};

            if(mat[i][j] > mat[i + 1][j])   return {i, j};
            if(mat[m - 1][j] > mat[m - 1 - 1][j])   return {m - 1, j};

            for(i = 0; i < m - 2; i++)
            {
                for(j = 0; 0 == i && j < n - 2; j++)
                {
                    if(n < 3)
                    {
                        if(mat[i][j] > mat[i][j + 1])
                            return {i, j};
                        else
                            return {i, j + 1};
                    }
                    if(mat[i][j] < mat[i][j + 1] && mat[i][j + 1] > mat[i][j + 2])
                        return {i, j + 1};
                }
                if(m < 3)
                {
                    if(mat[i][j] > mat[i + 1][j])
                        return {i, j};
                    else
                        return {i + 1, j};
                }
                if(mat[i][j] < mat[i + 1][j] && mat[i + 1][j] > mat[i + 2][j])
                    return {i + 1, j};
            }
        }
        
        // 四个角的数值
        if(mat[i + 1][j] < mat[i][j] && mat[i][j] > mat[i][j +1])   return {i, j};
        j = n - 1;
        if(mat[i][j - 1] < mat[i][j] && mat[i][j] > mat[i + 1][j])   return {i, j};
        i = m - 1;
        if(mat[i - 1][j] < mat[i][j] && mat[i][j] > mat[i][j - 1])   return {i, j};
        j = 0;
        if(mat[i - 1][j] < mat[i][j] && mat[i][j] > mat[i][j + 1])   return {i, j};

        for(i = 0; i < m - 2; i++)
        {
            // 左边
            j = 0;
            if(mat[i][j] < mat[i + 1][j] && mat[i + 1][j] > mat[i + 2][j]
            && mat[i + 1][j] > mat[i + 1][j + 1])
                return {i + 1, j};
            // 右边
            j = n - 1;
            if(mat[i][j] < mat[i + 1][j] && mat[i + 1][j] > mat[i + 2][j]
            && mat[i + 1][j] > mat[i + 1][j - 1])
                return {i + 1, j};
        }
        for(j = 0; j < n - 2; j++)
        {
            // 上边
            i = 0;
            if(mat[i][j] < mat[i][j + 1] && mat[i][j + 1] > mat[i][j + 2]
            && mat[i][j + 1] > mat[i + 1][j + 1])
                return {i, j + 1};
            // 下边
            i = m - 1;
            if(mat[i][j] < mat[i][j + 1] && mat[i][j + 1] > mat[i][j + 2]
            && mat[i][j + 1] > mat[i - 1][j + 1])
                return {i, j + 1};
        }
        
        // 中心
        for(i = 1; i < m - 1; i++)
        {
            for(j = 1; j <= n / 2; j++)
            {
                if(mat[i - 1][j] < mat[i][j] && mat[i][j - 1] < mat[i][j]
                && mat[i + 1][j] < mat[i][j] && mat[i][j + 1] < mat[i][j])
                    return {i, j};
                if(mat[m - i - 1][n - j] < mat[m - i][n - j]
                && mat[m - i][n - j - 1] < mat[m - i][n - j]
                && mat[m - i + 1][n - j] < mat[m - i][n - j]
                && mat[m - i][n - j + 1] < mat[m - i][n - j])
                    return {m - i, n - j};
            }
        }
        return {-1, -1};
    }
};

解法三：
??解法三是力扣官方给的一个解法，说是二分查找，但是我没有看懂，应该用到了某种数学公式。

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
    }
};