寻找峰值Ⅱ(LeetCode日记)

LeetCode-1901-寻找峰值Ⅱ

题目信息:

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

提示：

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

题解

方法：二分法；
令 $m$ 和 $n$ 分别为 $mat$ 的行数和列数。首先对于一维数组，因为任意两个相邻的格子的值都不相同，所以它的最大值必定是该一维数组的峰值。基于这一点，我们可以只考虑每一行的最大值，记第 $i$ 行的最大值为第 $j_i$列元素，如果 $mat[i][j_i]>mat[i?1][j_i]$且$mat[i][j_i]>mat[i+1][j_i]$(对于数组越界的情况，取 $?1$ 值），那么 $(i,j_i)$即为结果。
对于题目给定的条件，是否一定存在峰值呢？答案是肯定的。证明可以采用反证法：

如果不存在峰值，根据题目给定的条件，我们知道第0 行的最大值比它上面的格子(值为 ?1)大，那么初始时有 $i=0$ 行的最大值满足比上面格子大的条件。如果第 $i$行的最大值满足比它上面的格子大这一条件，那么根据不存在峰值的前提，我们有 $mat[i][ji]<mat[i+1][j_i]$，而$mat[i+1][j_i+1]\ge mat[i+1][j_i]>mat[i][j_i]\ge mat[i][j_{i+1}]$，从而我们有 $mat[i+1][j_i+1]>mat[i][j_{i+1}]$，即$i+1$也满足条件。基于以上推导，使用数学归纳法，当 $i=m?1$时，有$mat[m?1][j_{m?1}]>mat[m?2][j_{m?1}]$，而下面的格子值为$?1$，显然$(m?1,j_{m?1})$ 为峰值，与不存在峰值矛盾。

根据以上证明，我们也可以得出这样一个结论，即如果$i_1$行的最大值比它上面的格子大，$i_2$行比它下面的格子大，且$i_1\le i_2$ ，那么$[i_1,i_2]$之间一定存在峰值。基于这个结论，我们可以使用二分法来求解问题，初始时$low=0,high=m?1$:

1. 另$i=?\frac{low+high}{2}?$ ， 第$i$行的最大值为第$j$列。
2. 如果$mat[i][j]<mat[i?1][j]$ ，那么令$high=i?1$，继续步骤1。
3. 如果$mat[i][j]<mat[i+1][j]$ ，那么令$low=i+1$，继续步骤1。
4. 返回$(i,j)$为结果。

使用了这样的方法，我们的时间复杂度为$O(nlo{g}_m)$。
代码实现$(Python)$：

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m = len(mat)
        #n = len(mat[0])
        low = 0
        high = m-1
        while low <= high:
            i = (low + high)//2 
            j = mat[i].index(max(mat[i]))
            if i-1>=0 and mat[i][j] < mat[i-1][j]:
                high = i-1
                continue
            if i+1 < m and mat[i][j] < mat[i+1][j]:
                low = i + 1
                continue
            return [i,j]
        return None