題目出處
852. Peak Index in a Mountain Array
難度
easy
個人範例程式碼
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
if not arr:
return 0
start, end = 0, len(arr)-1
while(start + 1 < end):
mid = (start + end) // 2
if(arr[mid] < arr[mid+1]): # next go up, change start near to peak
start = mid
else: # next go down
end = mid
else:
if arr[start] >= arr[end]:
return start
else:
return end
算法說明
binary search，仔細討論會發現 mid 總共有 4 種狀況
- - [mid-1] < [mid] < [mid+1] ，正在往上走，把 start 移動往 mid (加速上坡)
- [mid-1] > [mid] > [mid+1] ，正在往下走，把 end 移動往 mid (減少下坡)
- [mid-1] < [mid] > [mid+1] ，paek 就是我們要的山峰
- [mid-1] > [mid] < [mid+1] ，valley 山谷，往兩側走都可
也可以再簡化，其實我們只要判斷一邊就好，
最後會縮小到一個範圍當中，其中一邊是高的，就是我們的局部最佳解。
移動方式示意圖
觀察 start, end 的移動方法
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理沒有輸入的時候，return 0
Boundary conditions
binary search 的結束條件