首页 > 代码库 > Leetcode: Find Peak Element
Leetcode: Find Peak Element
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.click to show spoilers.Note:Your solution should be in logarithmic complexity.
这道题还是有点麻烦的，要求O(logN)的时间复杂度，想到用二分查找。如果中间元素大于其相邻后续元素，则中间元素左侧(包含该中间元素）必包含一个局部最大值。如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。直到最后左边沿与右边沿相遇
这里有几点要说明：
1. 这里之所以选择只进行中间元素mid跟其相邻后续元素mid+1的大小讨论，而不涉及前一个元素mid-1，主要是方便。mid=(left+right)/2, 这个除法有一个floor效果在里面，即⌊(left+right)/2⌋。这样导致left和right不等时，index为mid和mid+1都存在，但是mid-1有可能小于0。这样每次当mid==0时，mid-1的元素都得特别讨论，麻烦。举个例子，比如left==0, right==1, mid==0, mid-1==-1, mid+1==1，不想讨论mid-1这种情况
2. 如果中间元素大于其相邻后续元素，说明中间元素左侧(包含该中间元素）必包含一个局部最大值，这时候中间元素是可能是局部最大点的，所以移动r = mid而不是r = mid-1; 而如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。这时中间元素肯定不会是局部最大点，所以移动l = mid + 1
3. 之所以要用左右边沿相遇作为找到条件，主要也是不想涉及到mid-1的问题。否则条件是num[mid]>num[mid+1] && num[mid]>num[mid-1]又要分情况mid==0了
4. 如果mid是一个valley, 比如[1, 2, 1, 6, 7], 这时候不知道该往哪边跳？这时候其实往左往右跳都可以。随便指定一个方向都可以，要么往左找到2，要么往右找到7（根据定义它也是peak value）。 因为只用找出一个，所以还是O(logN)
1 public class Solution { 2 public int findPeakElement(int[] num) { 3 int l = 0; 4 int r = num.length - 1; 5 while (l <= r) { 6 if (l == r) return l; 7 int mid = (l + r)/2; 8 if (num[mid] < num[mid+1]) { 9 l = mid + 1;10 }11 else {12 r = mid;13 }14 }15 return -1;16 }17 }
网上另一种老老实实比较mid跟前后元素大小关系的做法：
1 public int findPeakElement(int[] num) { 2 int n = num.length; 3 if (n <= 1) return 0; 4 // handle the first and last element in num[] 5 if (num[0] > num[1]) return 0; 6 if (num[n - 1] > num[n - 2]) return n - 1; 7 int left = 1, right = n - 2; 8 while (left <= right) { 9 int mid = (left + right) >> 1;10 if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) {11 return mid;12 } else if (num[mid] > num[mid + 1]) {13 right = mid - 1;14 } else {15 left = mid + 1;16 }17 }18 return -1;19 }
Leetcode: Find Peak Element