1. 二分
要求复杂度是O(logn)，说明了是要二分。
结果只要求一个值，因此二分到nums[i-1] < nums[i] < nums[i+1]的i即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (l == r)
ans = l++;
else if (mid > 0 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
ans = mid;
break;
} else if (nums[mid] < nums[mid + 1])
l = mid + 1;
else if (nums[mid] > nums[mid + 1])
r = mid - 1;
}
return ans;
}
};
|