发布于 2016-01-13 05:54:21 | 205 次阅读 | 评论: 0 | 来源: PHPERZ

这里有新鲜出炉的精品教程，程序狗速度看过来！

Leetcode 在线编程网站

leetcode 是一个美国的在线编程网站，上面主要收集了各大IT公司的笔试面试题，对于应届毕业生找工作是一个不可多得的好帮手。

---

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.

分析

这种找Peak Element的首先想到的是binary search, 因为有更优的时间复杂度，否则brute force O(n)的方法太直接了。

binary search的方法就是比较当前element与邻居，至于左邻居还是右邻居都可以，只要一致就行。不断缩小范围，最后锁定peak element.

这种类似题也有很多Follow up, 比如先增后减的数组怎么找指定元素，甚至先增后减再增的数组怎么找指定元素。

方法都是一样的，就是先得找到peak element的点，然后根据peak点将整个数组分成几部分，对于每个部分来说，是单调的，所以可以对每个部分分别用binary search来找元素。

复杂度

time: O(logn), space: O(1)

代码

public class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}