題目描述:給定整數陣列 nums,峰值元素是指嚴格大於其相鄰元素的元素(邊界元素的缺失鄰居視為負無窮大)。陣列中可能有多個峰值,只需回傳任意一個峰值的索引即可。要求時間複雜度 O(log n)。
解題思路:關鍵觀察:若 nums[mid] < nums[mid + 1],則 mid + 1 到 hi 之間必然存在至少一個峰值(因為值在上升,而右邊界視為負無窮,所以最終必然下降並形成峰值)。反之,若 nums[mid] > nums[mid + 1],則 lo 到 mid 之間必然存在至少一個峰值。
因此,每次將搜尋範圍縮減一半,始終保持「目標範圍內一定有峰值」的不變量,直到 lo == hi 為止,該位置即為峰值索引。
時間複雜度:O(log n) — 每次迭代將搜尋範圍縮減一半,滿足題目要求的對數時間複雜度。
空間複雜度:O(1) — 只使用兩個指標,不需要額外的資料結構。
1. Initialize lo = 0, hi = len(nums) - 1
2. While lo < hi:
a. Compute mid = lo + (hi - lo) / 2
b. If nums[mid] < nums[mid + 1]:
- Ascending slope: peak must be to the right, set lo = mid + 1
c. Else:
- Descending or at peak: peak is at mid or left, set hi = mid
3. Return lo (lo == hi, a valid peak index)方法一:線性掃描
從左到右掃描,找到第一個滿足 nums[i] > nums[i-1] 且 nums[i] > nums[i+1] 的元素(注意邊界處理)。時間複雜度 O(n),空間複雜度 O(1)。雖然能找到正確答案,但不符合題目要求的 O(log n)。
方法二:三元素比較二分搜尋(顯式判斷峰值)
在二分時先判斷 nums[mid] 是否同時大於左右鄰居,是則直接回傳;若右邊更大則往右移,若左邊更大則往左移。邏輯上更直觀,但需要額外的邊界條件處理,程式碼較長。時間複雜度同為 O(log n)。