1901. 寻找峰值 II --力扣 --JAVA

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

 题目

一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。

给你一个 从 0 开始编号 m x n 矩阵 mat ,其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值mat[i][j]返回其位置 [i,j]

你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。

要求必须写出时间复杂度为 O(m log(n))O(n log(m)) 的算法

解题思路

       1.对行进行二分处理,再对获取当前行的最大值,比较上下位置;

代码展示

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int n = mat.length;
        //右边界减一,避免额外判断mid + 1是否超出范围,在这个范围内每次更新左边界,最后二分结果为m - 1
        int left = 0; int right = n - 2;
        while (left <= right){
            int mid = (left + right) / 2;
            int maxIndex = findMax(mat[mid]);
            if(mat[mid][maxIndex] > mat[mid + 1][maxIndex]){
                //同上
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[]{left,findMax(mat[left])};
    }
    //寻找每行的最大值
    private int findMax(int[] data){
        int max = 0;
        for (int i = 1; i < data.length; i++){
            if(data[i] > data[max]){
                max = i;
            }
        }
        return max;
    }
}

image.gif


目录
相关文章
|
25天前
|
算法 Java
LeetCode(一)Java
LeetCode(一)Java
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
3月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
65 2
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
48 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
49 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
75 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
52 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
34 0
|
3月前
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
35 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
42 0