#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

/**
 * 162 找出数组中的峰值，左边和右边的数都小于它
 * A peak element is an element that is greater than its neighbors.
 * Given an input array nums, where nums[i] ≠ nums[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 nums[-1] = nums[n] = -∞.
 * 
 * Input: nums = [1,2,3,1]
 * Output: 2
 * 
 * Input: nums = [1,2,1,3,5,6,4]
 * Output: 1 or 5 
 * 找出数组的局部最大值，局部最大，不要求是全局最大。所以
 * 考虑比周围两个数字都大的数字，只需要和周围两个数字比较即可，和左右比较的话，
*/

/**
 * 方法 1，
 * 判断只要当前数字小于前一个数字，那么这个数字的前一个数字就是局部最大值
 * 返回前一个数的下标索引即可
 * 否则，最后返回数组最后一个数字的下标索引；
 */
int findPeakElement1(vector<int> &nums)
{
    for (int i = 1; i < nums.size(); ++i)
    {
        if (nums[i-1] > nums[i])
            return i - 1;
    }
    return nums.size() - 1;
}

/**
 * 方法 3，使用二分查找来做，这个题目要求找到峰值，那么只要是当前点的前一个和后一个数都小于它，那么就是峰值，输出即可，或者是左、右边界。
 * 首先一定有峰值，可证明，从左端点开始，前一个数默认是负无穷，然后第一个数大于它，只要第二个数是小于第一个数字，那么第一个就是峰值，否则数组
 * 一直上升到最右端点，最右端点的前一个点小于它，右侧默认是负无穷，所以峰值是右端点，即肯定存在峰值。
 * 这道题目使用二分来做，判断 mid 和 mid+1 之间的大小，如果mid >  mid+1,说明mid这个点右侧小于mid数，只要左侧也有一个数字小于mid数字即可
 * 这里分情况：
 * 如果mid左侧从的数字也小于mid，那么说明mid就是峰值，可以立即返回，但是mid左侧的数字大于mid，
 * 那么左侧一直大于mid，到最左端点出，出现峰值，所以峰值位置在左区间，那么r = mid
 * 同理，则 l = mid+1；
 * 最后返回l或r即可
*/
int findPeakElement2(vector<int> &nums)
{
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (nums[mid] > nums[mid + 1])
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}