原文链接: https://leetcode-cn.com/problems/find-a-peak-element-ii

英文原文

A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.

Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].

You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.

You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.

 

Example 1:

Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.

Example 2:

Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 105
• No two adjacent cells are equal.

中文题目

一个 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] <= 105
• 任意两个相邻元素均不相等.

通过代码

高赞题解

看注释

1.第一次美化题解

• 哈哈

2.还行

[Python3]
class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        l=r=0
        cl=len(mat)-1
        cr=len(mat[0])-1
        #螺旋上升
        #先下，再右，再上，在左
        #关键是flag
        while True:
            flag=True
            while l<cl and mat[l][r]<mat[l+1][r]:
                flag=False
                l+=1
            while r<cr and mat[l][r]<mat[l][r+1]:
                flag=False
                r+=1
            while l>0 and mat[l][r]<mat[l-1][r]:
                flag=False
                l-=1
            while r>0 and mat[l][r]<mat[l][r-1]:
                flag=False
                r-=1
            if flag:
                return [l,r]

统计信息

通过次数	提交次数	AC比率
1369	2188	62.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言