LeetCode题解：寻找峰值

Love The Way You Lie 2022-12-28 06:24 141阅读 0赞

# 寻找峰值（middle） #

> 更好的阅读体验应该是：
> 
> 1.  审题-思考
> 2.  答题
> 3.  整理-归纳

## 一、题目 ##

[LeetCode：162.寻找峰值][LeetCode_162.]

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

给定一个输入数组 `nums`，其中 `nums[i] ≠ nums[i+1]`，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

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

输入: nums = [1,2,1,3,5,6,4]
    输出: 1 或 5
    解释: 你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。

你的解法应该是 `O(logN)` 时间复杂度的。

## 二、基础模版 II ##

1.  确定初始的左右边界:
    
     *  `left`: 0
     *  `right`: nums.length-1
     *  `mid`: (left + (right - left) >> 1)
2.  查找条件需要访问元素的直接右邻居。
3.  使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
4.  保证查找空间在每一步中至少有 2 个元素。
5.  需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

## 三、题解 ##

**分析模版**

*  我们的目标是：寻找一段顺序区间内最大的元素
 *  我们拥有的访问区间不是顺序的，我们需要自己划分

**Javasciprt 代码**

/** * @param {number[]} nums * @return {number} */
    var findPeakElement = function(nums) { 
      let left = 0;
      let right = nums.length - 1;
      while (left < right) { 
        let mid = left + ((right - left) >> 1);
        // 这里需要保证区间内有2个元素
        if (nums[mid] < nums[mid + 1]) { 
          // 这证明 mid + 1 更有可能是当前区间的峰值，并且左侧是递减区间，可以抛弃
          left = mid + 1; //
        } else { 
          // 这证明 mid 更有可能是当前区间的峰值，并且右侧是递减区间，可以抛弃，但注意保留mid
          right = mid;
        }
      }
      return left;
    };

## 四、写在最后 ##

本文是二分查找-模版 II 的第二题，你可能意识到了，相对应的 leetcode 给他们标出中等的难度，加油！

如果对你有所帮助不妨给本项目的[github 点个 star][github _ star]，这是对我最大的鼓励～

**关于我**

*  花名：余光
 *  WX：j565017805
 *  沉迷 JS，水平有限，虚心学习中

**其他沉淀**

*  [JavaScript 版 LeetCode 题解][JavaScript _ LeetCode]
 *  [前端进阶笔记][Link 1]
 *  [CSDN][]

![yuguang-csdn-bottom.gif][]

[LeetCode_162.]: https://leetcode-cn.com/problems/find-peak-element/
[github _ star]: https://github.com/webbj97/summary
[JavaScript _ LeetCode]: https://webbj97.github.io/leetCode-Js/
[Link 1]: https://webbj97.github.io/summary/
[CSDN]: https://yuguang.blog.csdn.net/
[yuguang-csdn-bottom.gif]: /images/20221120/14c97c66affe4c038d5868145b5f436b.png