题目描述

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[0] = nums[n+1] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

输入格式

第一行一个整数 $n$;第二行有 $n$ 个互不相同的空格隔开的整数。

输出格式

一行一个整数，表示峰值所在的位置。数组位置从1 开始。

样例

样例 1：

4
1 2 3 1

3

解释：3 是峰值元素，你的函数应该返回其索引 3。

样例 2：

7
1 2 1 3 5 6 4

输出：2 或 6

解释：你的函数可以返回索引 2，其峰值元素为 2；   或者返回索引 6， 其峰值元素为 6。

数据规模

• $1 <= n <= 10^7$
• $-2^{31} <= nums[i] <= 2^{31} - 1$
• 对于所有有效的 i 都有 $nums[i] != nums[i + 1]$

PS：

因输入数据量较大，请使用较为快速的读入方式，比如：

int read()
{
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9')
    {                           // ch 不是数字时
        if (ch == '-') w = -1;  // 判断是否为负
        ch = getchar();         // 继续读入
    }
    while (ch >= '0' && ch <= '9')
    {                             // ch 是数字时
        x = x * 10 + (ch - '0');  // 将新读入的数字「加」在 x 的后面
        // x 是 int 类型，char 类型的 ch 和 '0' 会被自动转为其对应的
        // ASCII 码，相当于将 ch 转化为对应数字
        // 此处也可以使用 (x<<3)+(x<<1) 的写法来代替 x*10
        ch = getchar();  // 继续读入
    }
    return x * w;  // 数字 * 正负号 = 实际数值
}