這題題目在這裡:
Peak Index in a Mountain Array - LeetCode
題目會給定一個陣列，陣列裡面的元素分布就像一座山峰。最大值的左邊都是上坡段，最大值的右邊都是下坡段。
要求我們找出陣列裡面的絕對極大值(absolute max value)所在的陣列索引
也就是說當下這個元素，大於左邊鄰居的元素值，也大於右邊鄰居的元素值。
nums[i] > nums[i-1] > ... > nums[0] 且
nums[i] > nums[i+1] > ... > nums[n-1]
答案只會有一組解。
測試範例:
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
約束條件:
Constraints:
3 <= arr.length <= 1050 <= arr[i] <= 106arris guaranteed to be a mountain array.
演算法:
先回顧一個基本性質，在已經排序好的陣列元素裡面搜尋，適合使用二分搜尋法。
基本上和前一題用到的都是同樣的觀念，和鄰居去比較，
每次判斷是上坡還是下坡，去決定搜尋的方向。
假如現在是上坡，絕對最大值肯定在我的右邊。
假如現在是下坡，絕對最大值肯定在我的左邊。
程式碼:
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
def helper(nums, left, right):
if left == right:
# base case:
return left
mid = ( left + right ) // 2
# general case
if nums[mid] > nums[mid+1]:
# peak is either nums[mid] or on the left hand side
return helper(nums, left, mid)
else:
# peak is either nums[mid+1] or on the right hand side
return helper(nums, mid+1, right)
return helper( arr, 0 , len(arr)-1)
時間複雜度:
O( log n ) : 每次都能淘汰一半不可能的區間，最多花費O( log n )次可以找到絕對最大值，也就是山峰。
空間複雜度:
O( log n ): 遞迴stack深度最大為O( log n )，最多花費O( log n )層可以抵達終止條件。
這題學完，記得去複習經典的Binary search、Search a 2D Matrix、Sqrt(x)、
Find Peak Element，背後的二分搜尋法原理和對半切從中心點去逼近解答、目標值的想法都是相通的喔!
Reference:
