There is an integer array which has the following features:
- The numbers in adjacent positions are different.
- A[0] < A[1] && A[A.length - 2] > A[A.length - 1].
We define a position P is a peek if:
A[P] > A[P-1] && A[P] > A[P+1]
Find a peak element in this array. Return the index of the peak.
Notice
The array may contains multiple peeks, find any of them.
Example
Given [1, 2, 1, 3, 4, 5, 7, 6]
Return index 1 (which is number 2) or 6 (which is number 7)
Challenge
Time complexity O(logN)
LeetCode上的原题，请参见我之前的博客Find Peak Element。
解法一：
class Solution { public: /** * @param A: An integers array. * @return: return any of peek positions. */ int findPeak(vector<int> A) { int left = 0, right = A.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (A[mid] < A[mid + 1]) left = mid + 1; else right = mid; } return right; } };
解法二：
class Solution { public: /** * @param A: An integers array. * @return: return any of peek positions. */ int findPeak(vector<int> A) { for (int i = 1; i < A.size(); ++i) { if (A[i] < A[i - 1]) return i - 1; } return A.size() - 1; } };
本文转自博客园Grandyang的博客，原文链接：求数组的峰值[LintCode] Find Peak Element ，如需转载请自行联系原博主。
