題目

852. 山脈數組的峰頂索引 - 力扣（LeetCode）

思路

使用二分查找來定位峰頂

對于中間元素，比較它與其右側元素的大小：

• 如果?arr[mid]?< arr[mid+1]，說明我們在上坡階段，峰頂在右側

• 如果?arr[mid] > arr[mid+1]，說明我們在下坡階段，峰頂在左側或當前位置

不斷縮小搜索范圍，直到?left == right，此時指向的就是峰頂位置

時間復雜度和空間復雜度

時間復雜度：O(log n)，符合題目要求

空間復雜度：O(1)

正確的寫法

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0;int right = arr.size()-1;while(left < right){int mid = left + (right-left)/2;if(arr[mid] < arr[mid+1]){left = mid+1;}else if(arr[mid] > arr[mid+1]){right = mid;}}return left;}
};