75. 寻找峰值

题目

75. 寻找峰值

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

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

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

给出数组[1, 2, 1, 3, 4, 5, 7, 6]返回1, 即数值 2 所在位置, 或者6, 即数值 7 所在位置.
挑战

Time complexity O(logN)
注意事项

    It's guaranteed the array has at least one peak.
    The array may contain multiple peeks, find any of them.
    The array has at least 3 numbers in it.

解析

• 分析

分析
任意选取数组中的一个元素A[n]（n!=0&&n!=A.length-1），一共可能出现四种情况：
1 A[n-1]< A[n],A[n+1]>A[n]，即A[n]处在一个递增序列中。此时大于n的位置中必存在峰值。
2.A[n-1]> A[n],A[n+1]< A[n]，即A[n]处在一个递减序列中。此时小于n的位置中必存在峰值。
3.A[n-1]> A[n],A[n+1] >A[n],即A[n]处在一个“低谷”，分析题目给定的数组的条件可知此时n左右两边都存在峰值。
4. A[n-1]< A[n],A[n+1]< A [n]，此时n即我们要找的峰值。

经过以上分析，便可以用二分法简单的寻找到一个峰值。
另外，若数组中存在n个“低谷”，就会有n+1个峰值，二分搜索的过程中每次碰到低谷，在代码中只选择了其左边或右边一种情况，因此只能找到一个峰值。不过这已经满足题目要求。

• AC代码

class Solution {
public:
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    int findPeak(vector<int> &A) {
        // write your code here
        int n=A.size();
        int l=0;
        int r=n-1;
        if(n==3)
            return 1;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(A[mid]>A[mid-1]&&A[mid+1]<A[mid])
                return mid;
            else if(A[mid-1]<A[mid]&&A[mid]<A[mid+1]) //递增序列
                l=mid+1;
            else if(A[mid+1]>A[mid]&&A[mid]>A[mid-1]) //递减序列
                r=mid-1;
            else  //波谷或者相等
                r=mid-1;
        }
        if(l>0&&A[l-1]<A[l]&&A[l]>A[l+1])
            return l;
        if(r<n-1&&A[r-1]<A[r]&&A[r]>A[r+1])
            return r;
            
        return -1;
    }
};

参考

• 75. 寻找峰值