【每日一题】【12.19】1901.寻找峰值Ⅱ

🔥博客主页： A_SHOWY
🎥系列专栏：力扣刷题总结录数据结构云计算数字图像处理力扣每日一题_

1.题目链接

1901. 寻找峰值 IIhttps://leetcode.cn/problems/find-a-peak-element-ii/

2.题目描述

看到这个时间复杂度就知道和昨天的题目一样要用二分了，比昨天的难度稍微大一点，这个题目是一个二维找峰值了。不过整体思路差不多。

3.题目分析解答

第一步

我们要明确如果i1行的最大值比它上面的格子大，同时i2行比它下面的格子小，i1<=i2.那么在【i1，i2】之间一定存在峰值。我们可以用二分法求解

第二步

构造二分法：设置low为0，high为m-1，m为这个数组的行数。并且设置i（mid）为二分之low+high。第i行的最大值为第j列。

如果mat[i][j] < mat[i-1][j],那么high = i-1；继续‘

如果mat[i][j] < mat[i+1][j],那么low = i + 1；继续

返回（i，j ）的结果

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size();
        int low = 0;int high = m -1;
        while(low <= high){
            int i = (low + high)/2;
            int j = max_element(mat[i].begin(),mat[i].end()) - mat[i].begin();//找到第i行的最大值
            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{};
    }
};

有几个需要注意点

我们使用这个方法的前提是因为任意两个相邻的格子的值都不相同，所以它的最大值必定是该一维数组的峰值。基于这一点，我们可以只考虑每一行的最大值。

 int j = max_element(mat[i].begin(),mat[i].end()) - mat[i].begin();//找到第i行的

我们又用到了这个max_element求数组中最大值的函数
注意二分法时的取值范围


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

注意在第一个if中由于high是i-1，因为是减法操作所以要保证i-1大于等于下边界0

而第二个if中low是i+1，不能超过它的上边界m，这才是if中需要注意的条件