寻找峰值

你给出一个整数数组(size为n)，其具有以下特点：

相邻位置的数字是不同的A[0] < A[1] 并且 A[n - 2] > A[n - 1]

假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。

样例

样例 1: 输入: [1, 2, 1, 3, 4, 5, 7, 6] 输出: 1 or 6 解释: 返回峰顶元素的下标 样例 2: 输入: [1,2,3,4,1] 输出: 3

挑战

Time complexity O(logN)

注意事项

数组保证至少存在一个峰如果数组存在多个峰，返回其中任意一个就行数组至少包含 3 个数

思路:

重在理解题意,如果一个数组中第一个元素小于第二个元素,最后一个元素小于倒数第二个元素的话中间一定会有峰值

所以我们这里如下设置:

left是第二元素,right是倒数第二个元素

每次都取left和right中间的元素,判断这个元素如果比左右的元素都要大直接返回,因为找到一个就可以返回了

如果这个元素小于左边的元素,大于右边的元素,说明他满足了尾巴的这个性质,但是不满足头这个性质.所以从mid之前的元素可以作为一个独立的数组,同样具有上面的性质.此时的right指向mid前面的元素,也就是数组中的倒数第二个元素 

如果这个元素 大于左边的元素而小于右边的元素,说明他满足头这个性质而不满足尾巴这个性质,所以从mid开始后面的元素成为一个独立的数组,left指向mid后的一个元素,也就是数组的第二个元素.

 

class Solution { public: /** * @param A: An integers array. * @return: return any of peek positions. */ int findPeak(vector<int> &A) { // write your code here int l = 1, r = A.size()-2; while (l <= r) { int mid = (l + r) / 2; if (A[mid] > A[mid-1] && A[mid] > A[mid+1]) return mid; if (A[mid] > A[mid-1]) l = mid + 1; else r = mid - 1; } return -1; } };