題目出處
難度
medium
個人範例程式碼
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if not nums:
return 0
start, end = 0, len(nums) - 1
while(start + 1 < end):
mid = (start + end) // 2
if(nums[mid] >= nums[mid+1]):
end = mid
else:
start = mid
else:
if(nums[start] >= nums[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 山谷，往兩側走都可
也可以再簡化，其實我們只要判斷一邊就好，
最後會縮小到一個範圍當中，其中一邊是高的，就是我們的局部最佳解。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理沒有輸入的時候，return 0 (題目有保證不會有輸入問題)
Boundary conditions
binary search 的結束條件