1901. 寻找峰值 II (中等,二分)

2023-12-19 21:49:53

在这里插入图片描述
和昨天的差不多,但是没想到这么做,还是太菜了

  1. 以O(n)的时间来找到每一行的最大值,显然此处的左右元素都比它小,只用分析它的上下元素,因为要寻找峰值,所以需要分析它不为峰值的情况
  2. 如果它的下方的元素比它大,那我们就找到它下面的那一行,有两种情况,一是比它大的元素恰好是下一行最大的元素,那么此时该元素的上,左,右都比它小,只需要考虑下面的元素就可以了;第二种情况,比它大的元素不是下一行最大的元素,由于它时这一行最大的元素,下一行不是最大的元素都比它大了,那么下一行最大元素必定比这一行所有元素都大,此时情况也是该元素的上,左,右都比它小,只需要考虑下面的元素就可以了
  3. 如果它的上方的元素比它大,同理。
  4. 类似于昨天的思路来二分搜索即可
class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m = len(mat)
        low, high = 0, 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 

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