付費限定文章

一魚多吃 用 二分搜尋 來尋找相對最大值 Find Peak Element Leetcode #162_精選75題解

Henry Be on Unsplash

這題題目在這裡:

Find Peak Element - LeetCode

題目會給定一個陣列，裡面有大有小，可以把數字的大小類比成高度

要求我們找出陣列裡面的相對極大值(relative max value)所在的陣列索引

也就是說當下這個元素，大於左邊鄰居的元素值，也大於右邊鄰居的元素值。

nums[i] > nums[i-1] 且

nums[i] > nums[i+1]

答案可能不只一組，返回任何一組合法的皆可。

測試範例:

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

約束條件:

Constraints:

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.

演算法:

可以把陣列的數值當成每一個高峰和低谷，我們要做的就是定位高峰所在的位置。

因此，我們可以每次和右邊的鄰居做比較，有兩種情況。

情況一:

假如我比右邊的鄰居還大，代表高峰值一定落在我的左邊或者剛好是我自己，因此捨棄右半部，收縮右邊界，窗口往左邊移動。

情況二:

假如我比右邊的鄰居還小或者相等，代表高峰值一定落在我的右邊，而且高峰值不可能是我自己(因為我比較小)，因此捨棄左半部，收縮左邊界，窗口往右邊移動。

終止條件:

當左右邊界都相等時，這時候只剩下一個元素，這個元素就是相對最大值，也就是高峰值(peak element)。