一魚再吃 用 二分搜尋 來尋找平面相對高點 Find a Peak Element II_Leetcode #1901

Anthony DELANOIX on Unsplash

這題的題目在這裡

題目會給定一個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.length
• n == mat[i].length
• 1 <= 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