一魚再吃 用 二分搜尋 來尋找平面相對高點 Find a Peak Element II_Leetcode #1901
題目會給定一個2D 二維的矩陣，矩陣內的元素值代表對應的高度，要求我們找出相對最高點，也就是(大樓)高度大於N4 東、南、西、北 四個鄰居的索引值。
題目保證矩陣內相鄰的元素值都不相同，也又是相鄰的兩兩相比較，一定有一個比較高，有一個比較矮。
答案可能不只一組，返回任何一組合法的皆可。
題目要求我們的演算法，必須在O( m log n ) 或者 O( n log m )時間複雜度之內。
註:
其實經驗累積久了，看到m log n 這種order的時間複雜度，就會想到二維平面的二分搜尋法，這是一個很強烈的提示。
測試範例:
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.lengthn == mat[i].length1 <= m, n <= 500 矩陣一定有內容，保證不是空陣列1 <= mat[i][j] <= 105- No two adjacent cells are equal. 每個相鄰的元素都不同
演算法:
承接一開始題目的限制，也是提示，複雜度必須在O( m log n ) 或者 O( n log m )之內。
一開始先剖半，找到寬度的中心點，從中心點那條column開始找，
接著，在垂直方向找出有最大值的那一個row，再和那個row的左右鄰居做比較。
題目又保證矩陣內相鄰的元素值都不相同，也又是相鄰的兩兩相比較，一定有一個比較高，有一個比較矮。
所以，比較之後，往大的那邊移動(因為我們今天要找的是相對最大值，也就是擁有相對最高的矩陣索引值)
每次砍半，捨去一半不可能的區間，直到找到相對最大值，然後返回該點的索引值，就是答案。
程式碼:
class Solution(object):
def findPeakGrid(self, mat):
# height and width of input matrix
h, w = len(mat), len(mat[0])
# Window of binary search, initialized as boundary
left, right = 0, w-1
# Find largest column by binary search
while left <= right:
cur_col = left + ( right - left ) // 2
# Find largest row by brute force linear scan on row-wise
cur_max = -math.inf
cur_row = -1
for row in range(h):
if mat[row][cur_col] > cur_max:
cur_max = mat[row][cur_col]
cur_row = row
# Binary seach to find peak element on column-wise
leftLarger = (cur_col -1 >= 0) and mat[cur_row][cur_col-1] > mat[cur_row][cur_col]
rightLarger = (cur_col +1 <= (w-1) ) and mat[cur_row][cur_col+1] > mat[cur_row][cur_col]
if leftLarger:
right = cur_col-1
elif rightLarger:
left = cur_col+1
else:
return [cur_row, cur_col]
return [-1, -1]
時間複雜度:
O( h log w ) = O( m log n )
垂直方向找最大值耗費O( m )
內層針對水平方向做二分搜尋法，耗費O( log n )
空間複雜度:
O( 1 ) 只使用固定尺寸的臨時變數，所占用的空間為常數級別O( 1 )
這題學完，記得去複習經典的Binary search、
強烈推薦複習這題-> Search a 2D Matrix、Sqrt(x)、Find Peak Element，
背後的二分搜尋法原理和對半切從中心點去逼近解答、目標值的想法都是相通的喔!
Reference:
[1] Python O( h log w ) by 2D binary search [w/ Comment] - Find a Peak Element II - LeetCode
