2023.12.19力扣每日一题

2023-12-20 03:22:43

题目来源

力扣每日一题;题序:1901

我的题解

方法一 暴力法

对于每一个点都判断四周是否比自己小,若是则直接返回该点坐标,否则继续寻找。

时间复杂度: O(mn)。
空间复杂度:O(1)。只有一个表示方向的常量空间消耗

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m=mat.length;
        int n=mat[0].length;
        //遍历每个点
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(check(mat,i,j)){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{-1,-1};
    }
    int[][] pos={{1,0},{0,1},{-1,0},{0,-1}};
    public boolean check(int[][] mat,int i,int j){
        for(int k=0;k<4;k++){
            int x=i+pos[k][0];
            int y=j+pos[k][1];
            // 若遍历的四周是边界,则必然满足
            if(x<0||x>=mat.length||y<0||y>=mat[0].length)
                continue;
            // (i,j)的四周比(i,j)大,则(i,j)不可能是峰值
            if(mat[x][y]>=mat[i][j])
                return false;
        }
        return true;
    }
}
方法二 二分查找

先二分找行,找到行之后需要计算出当前行的最大值所在的列,然后看列前列后元素是否都小于当前行的最大值,若是则直接返回当前的行和列;若列前元素比当前最大值大,则需要在前面的行查找峰值;若列后的元素比当前最大值大,则需要在后面的行查找峰值。

时间复杂度:O(mlogn)
空间复杂度:O(1)

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m=mat.length;
        int n=mat[0].length;
        
        int left=0,right=m-1;
        while(left<=right){
            int mid=((right-left)>>1)+left;
            int j=-1,maxE=-1;
            //找行的最大值
            for(int i=0;i<n;i++){
                if(mat[mid][i]>maxE){
                    j=i;
                    maxE=mat[mid][i];
                }
            }
            //判断最大值所在列的上方元素是否大于当前值,若大于则当前值不是峰值,而需要在上方寻找
            if(mid-1>=0&&mat[mid][j]<mat[mid-1][j]){
                right=mid-1;
                continue;
            }
            //判断最大值所在列的下方元素是否大于当前值,若大于则当前值不是峰值,而需要在下方寻找
            if(mid+1<m&&mat[mid][j]<mat[mid+1][j]){
                left=mid+1;
                continue;
            }
            return new int[]{mid,j};
        }
        return new int[]{-1,-1};
    }

}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

文章来源:https://blog.csdn.net/weixin_42075274/article/details/135086232
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。