題目來(lái)源
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
一看這題目待讳，挺簡(jiǎn)單的啊锌奴，最先想到的方法就是從前往后遍歷叉瘩，遍歷到該元素比周圍元素大或者小的就返回歧匈。第一個(gè)和最后一個(gè)特殊處理一下。直接AC了。復(fù)雜度O(n)。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
if (n == 1 || nums[0] > nums[1])
return 0;
if (nums[n-1] > nums[n-2])
return n-1;
for (int i=1; i<n-1; i++) {
if (nums[i] < nums[i-1] && nums[i] < nums[i+1])
return i;
if (nums[i] > nums[i-1] && nums[i] > nums[i+1])
return i;
}
return -1;
}
};
好吧，肯定有O(logN)的做法烛谊，看看去。
先來(lái)個(gè)O(n)的环壤，但是簡(jiǎn)潔的很啊==
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
for (int i=1; i<n; i++) {
if (nums[i] < nums[i-1])
return i-1;
}
return n-1;
}
};
還有O(logN)的晒来，之前就沒(méi)想到可以用二分查找，這不是無(wú)序的嗎郑现？怎么用二分呢湃崩？看看代碼就知道了。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1;
int mid1 = 0, mid2 = 0;
while (l < r) {
mid1 = (l + r) / 2;
mid2 = mid1 + 1;
if (nums[mid1] < nums[mid2])
l = mid2;
else
r = mid1;
}
return l;
}
};
實(shí)際上也不難看懂接箫，比如找到mid1 and mid2是遞增的攒读，那么mid2及其后面一定有個(gè)極值點(diǎn)，因?yàn)樽詈笠稽c(diǎn)是遞減的辛友。同理mid1 and mid2是遞減的薄扁，那么mid1及其前面一定有個(gè)極值點(diǎn)，因?yàn)榈谝稽c(diǎn)是遞增的邓梅。
