AcWing 1611. 寻找峰值
宋标 Lv5
  2022-08-18 02:31:19 2022-08-18 02:31    

题目

峰值定义为比左右相邻元素大的元素。

给定一个长度为 的数组 ，数组下标从0开始，保证 ，请找出该数组的峰值，并返回峰值的下标。

数组中可能包含多个峰值，只需返回任意一个即可。

假定 nums[-1] = nums[n] = -∞。

本题中数组是隐藏的，你可以通过我们预设的 int 函数 query 来获得数组中某个位置的数值是多少。

例如， 即可获得下标为 的元素的值。

注意：

query 函数的调用次数不能超过 。

数据范围

，
数组中的整数在 int 范围内。

输入样例1：

[1, 2, 3, 1]

输出样例1：

2

输入样例2：

[1, 2, 1, 3, 5, 6, 4]

输出样例2：

1

样例解释

对于样例 ， 是峰值，其下标为 。

对于样例 ， 和 是峰值，下标为 和 ，输出任意一个均可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Forward declaration of queryAPI.
// int query(int x);
// return int means nums[x].

class Solution {
public:
    int findPeakElement(int n) {
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            // a[m + 1] 大于 a[m], m + 1 ~ R 一定有峰值
            // a[m - 1] 小于 a[m], L ~ m 一定有峰值
            if (mid + 1 < n && query(mid + 1) > query(mid)) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};
 评论