<jupyter_start><jupyter_text>1901. Find a Peak Element II  ContentA 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.&nbsp;Example 1:Input: mat = [[1,4],[3,2]]Output: [0,1]Explanation:&nbsp;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:&nbsp;Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.&nbsp;Constraints:	m == mat.length	n == mat[i].length	1 &lt;= m, n &lt;= 500	1 &lt;= mat[i][j] &lt;= 105	No two adjacent cells are equal.  Difficulty: Medium, AC rate: 59.9% Question Tags:- Array- Binary Search- Divide and Conquer- Matrix Links: 🎁 [Question Detail](https://leetcode.com/problems/find-a-peak-element-ii/description/) | 🎉 [Question Solution](https://leetcode.com/problems/find-a-peak-element-ii/solution/) | 💬 [Question Discussion](https://leetcode.com/problems/find-a-peak-element-ii/discuss/?orderBy=most_votes) Hints:Hint 0  🔍Let's assume that the width of the array is bigger than the height, otherwise, we will split in another direction.Hint 1  🔍Split the array into three parts: central column left side and right side.Hint 2  🔍Go through the central column and two neighbor columns and look for maximum.Hint 3  🔍If it's in the central column - this is our peak.Hint 4  🔍If it's on the left side, run this algorithm on subarray left_side + central_column.Hint 5  🔍If it's on the right side, run this algorithm on subarray right_side + central_column  Sample Test Case[[1,4],[3,2]] ---What's your idea?类似 162，按行二分，行内找最大的元素 O(n), 总时间复杂度 O(n * log(m))同样在 [MIT6.006](https://www.youtube.com/v/HtSuA80QTyo) 里有讲解---<jupyter_code>from typing import List

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m = len(mat)
        if m == 1:
            max_j, _ = max(enumerate(mat[0]), key=lambda tup: tup[1])
            return [0, max_j]
        
        middle_row = m // 2
        max_j, _ = max(enumerate(mat[middle_row]), key=lambda tup: tup[1])
        if middle_row > 0 and mat[middle_row-1][max_j] > mat[middle_row][max_j]:
            return self.findPeakGrid(mat[:middle_row])
        elif middle_row < m - 1 and mat[middle_row+1][max_j] > mat[middle_row][max_j]:
            result = self.findPeakGrid(mat[middle_row+1:])
            return [sum(p) for p in zip(result, [middle_row+1, 0])]
        else:
            return [middle_row, max_j]
s = Solution()

print(s.findPeakGrid([[1,2,3]]) == [0, 2])
r = s.findPeakGrid([[1,4],[3,2]])
print(r == [1, 0] or r == [0, 1])
r = s.findPeakGrid([[10,20,15],[21,30,14],[7,16,32]])
print(r == [1, 1] or r == [2, 2])
r = s.findPeakGrid([[47,30,35,8,25],[6,36,19,41,40],[24,37,13,46,5],[3,43,15,50,19],[6,15,7,25,18]])
print(r == [0, 2] or r == [3, 3])
import sys, os; sys.path.append(os.path.abspath('..'))
from submitter import submit
submit(1901)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup