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

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 10^5
• 任意两个相邻元素均不相等.

解答

思路

https://leetcode.cn/problems/find-a-peak-element-ii/solutions/2571587/tu-jie-li-yong-xing-zui-da-zhi-pan-duan-r4e0n/

暴力做法：由 人往高处走 的思想，每次从左上角出发，每次都往四周比当前位置大的数字走，直到走到一个峰顶。这样做最坏的时间复杂度为 $O(mn)$，不符合要求。

如果按照 LC162-寻找峰值 的思路进行二分：

• 为什么要求最大值？
• 为什么必然包含峰顶？

按照 人往高处走 的思路，那么必然存在一条从 11 开始出发 递增的路径，可以到达峰顶，同时这条路径上的所有数都大于 10，因此这条路径不会穿过 [10, 9, 8, 7] 这一行，因为 10 是这一行的最大值。因此最后两行一定包含一个峰顶。

如果这一行的最大值比下面的相邻数字大呢？

有两种情况：

• 10 本身就是峰顶
• 峰顶在 10 上面两行

因此我们可以二分 包含峰顶 的行号 $i$：

• 如果 mat[i] 的最大值比它下面的相邻数字小，那么存在一个峰顶，它的行号大于 i，缩小二分范围，更新二分区间的左端点 left = i + 1
• 如果 mat[i] 的最大值比它下面的相邻数字大，那么存在一个峰顶，它的行号大于等于 i，缩小二分范围，更新二分区间的右端点 right = i

代码

由于要和下面的相邻数字比较，因此我们区间范围是 [0, n - 2]。

闭区间

cpp

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

public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int left = 0;
        int right = mat.size() - 2;

        while (left <= right) {
            int i = left + right >> 1;
            int j = indexOfMax(mat[i]);

            if (mat[i][j] > mat[i + 1][j]) {
                right = i - 1;
            }
            else {
                left = i + 1;
            }
        }

        return {left, indexOfMax(mat[left])};
    }
};

python

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        left = 0
        right = len(mat) - 2

        while left <= right:
            i = (left + right) // 2
            j = mat[i].index(max(mat[i]))

            if mat[i][j] > mat[i + 1][j]:
                right = i - 1
            else:
                left = i + 1

        i = left
        
        return [i, mat[i].index(max(mat[i]))]

左闭右开区间

cpp

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

public:
    vector<int> findPeakGrid(vector<vector<int>> &mat) {
        int left = 0;
        int right = mat.size() - 1;
        
        while (left < right) {
            int i = left + right >> 1;
            int j = indexOfMax(mat[i]);

            if (mat[i][j] > mat[i + 1][j]) {
                right = i;
            }
            else {
                left = i + 1;
            }
        }
        return {left, indexOfMax(mat[left])};
    }
};

python

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        left, right = 0, len(mat) - 1
        
        while left < right:
            i = (left + right) // 2
            mx = max(mat[i])
        
            if mx > mat[i + 1][mat[i].index(mx)]:
                right = i  # 峰顶行号 <= i
            else:
                left = i + 1  # 峰顶行号 > i
        
        i = left

        return [i, mat[i].index(max(mat[i]))]