数组篇2_寻找峰值解题思路

来源：LeetCode

难度：中等

描述：

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

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

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

进阶：你可以实现时间复杂度为 O(logN) 的解决方案吗？

示例1：

输入：nums=[1,2,3,1]
输出：2
解释：3是峰值元素，你的函数应该返回其索引2

示例2：

输入：nums=[1,2,1,3,5,6,4]
输出：1或5

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

提示：

• 1  <=  nums.length  <=  1000
• -231  <=  nums[i]  <= 231 – 1
• 对于所有有效的 i 都有 nums[i]  !=  nums[i + 1]

分析：所谓峰值，就是一个元素比左右两个值大，首先想到的是咱直接遍历一遍数组，将每个元素与后面元素进行比较即可，如果比后面大直接输出该元素下标即可，如果已是最后一个元素，直接输出即可；同时，咱可以将数组元素分为以下几类，其中第三类和第四类又可拆分为第一类和第二类（根据提示相等可以局部相等可以不考虑），那么对于局部递增递减咱可以用二分法来解题，且只要找到其中一个峰值就行，所以咱只需查找存在大值的那一部分元素即可

题外话：遇到题目要求时间复杂度为O(logN)的情况，咱大可以往二分法上靠

解题

方法一：顺序遍历法

思路：由于找的是局部峰值，且 nums[-1] = nums[n] = -∞ ，那么咱们每个元素只要和下一个元素比较即可，如果比后面一个大，说明是局部凸起的形状，咱直接输出本元素下标即可，如果下一个元素都比前一个大，说明是递增的形状，直接输出最后一个即可

代码：

1public int findPeakElement(int[] nums) {
2    for (int i = 0; i < nums.length - 1; i++) {
3        if (nums[i] > nums[i + 1]) {
4            return i;
5        }
6    }
7    return nums.length - 1;
8}

时间复杂度：O(n)

空间复杂度：O(1)

方法二：递归 + 二分

思路：如上图，一共有4种情况，其中局部凸起和下陷又可拆分为局部递增和递减，并且题目要求找到任意一个峰值即可，所以我们只需要考虑左右元素大的那一侧即可，通过二分不断缩短查询范围直到只有一个元素即是需要的元素

代码：

 1public int findPeakElement(int[] nums) {
 2    return search(nums, 0, nums.length - 1);
 3}
 4public int search(int[] nums, int l, int r) {
 5    if (l == r) {
 6        return l;
 7    }
 8    //取中间位置
 9    int mid = (r - l) / 2 + l;
10    if (nums[mid] > nums[mid + 1]) {
11        //往右为下降趋势，查左边即可
12        return search(nums, l, mid);
13    }
14    //往右为上升趋势，查右边即可
15    return search(nums, mid + 1, r);
16}

时间复杂度：O(log2(n))

空间复杂度：O(log2(n))

方法三：递归 + 二分

思路：和方法二思路一致，只是通过循环的实现方式替代递归，在本题中可以降低复杂度

代码：

 1public int findPeakElement(int[] nums) {
 2    int l = 0, r = nums.length - 1;
 3    while (l < r) {
 4        //取中间
 5        int mid = (r - l) / 2 + l;
 6        if (nums[mid] > nums[mid + 1]) {
 7            //往右为下降趋势，查左边即可
 8            r = mid;
 9        } else {
10            //往右为上升趋势，查右边即可
11            l = mid + 1;
12        }
13    }
14    return l;
15}

时间复杂度：O(log2(n))

空间复杂度：O(1)