从 O(N) 优化到 O(logN)，你的第一想法是什么？

约定不等于承诺〃 2023-05-28 06:41 2阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

今天分享的题目来源于 LeetCode 第 162 号问题：寻找峰值。通过这道题目，你又能再次复习二分法的用处。

### 题目描述 ###

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

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

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

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

**示例 1:**

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

**示例 2:**

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

**说明:**

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

### 题目解析 ###

目让你找出一个数组中的 `peak element`，数组中可能存在一个或者多个 `peak element`，但是你只需要找出一个就好。

这道题目最直接的办法就是直接遍历一遍数组，然后将每个元素与其左右相邻的元素进行比较，符合条件输出即可。

显而易见，这么做时间复杂度是 `O(n)`，n 为数组中元素的个数。

有没有更快的方法呢？

比 `O(n)` 还要快的话，一般来说只会是 `O(lgn)` 和 `O(1)`，`O(1)` 显然是不可能的，那么就只剩下 `O(lgn)`。

通过这个时间复杂度，我相信你应该知道用什么样的算法，没错就是**二分查找**。

那么用二分查找怎么做呢？

题目描述中有一个细节是，我们可以认为 `arr[-1] == arr[n] == -Inf`，**也就是两头的元素只需要和它相邻的一个元素比较即可**。再进一步想，这里其实还隐藏了一个信息，就是我们**二分查找顺着递增的方向去找的话就一定能够找到峰值**。

如果能够分析到这里，那么这道题基本上就算是解决了。

### 动画描述 ###

### 参考代码 ###

//五分钟学算法
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
    
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
    
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            } else if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1]) {
                start = mid;
            } else {
                end = mid;
            }
        }
    
        if (nums[start] > nums[end]) {
            return start;
        }
    
        return end;
    }

**END**

--------------------

![format_png 2][]

● [答应我，别再if/else走天下了可以吗][if_else]

[● ][Link 1][如何利用寒假的时间来准备2020年的蓝桥杯?][2020]

● [给大家推荐一款软件][Link 2]

● [关于计算机读研的小建议][Link 3]

![format_png 3][]

点“在看”你懂得

![format_png 4][]

[format_png]: /images/20230528/85fa9befc2024a6293e092259358e194.png
[format_png 1]: /images/20230528/9311da3d519d4a9da41cacca8327962f.png
[format_png 2]: /images/20230528/aca1385c25bf435bb60d49cce0727334.png
[if_else]: https://blog.csdn.net/kexuanxiu1163/article/details/104140332
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[2020]: https://blog.csdn.net/kexuanxiu1163/article/details/104140333
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6038cd79e92ec7f54e62aaf535c402eed0be07e97d1fdbced663280d2dccdda047ee099c&idx=1&mid=2247487417&scene=21&sn=13d97404f7f5700bb901171e4d9f91e4#wechat_redirect
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/104078939
[format_png 3]: /images/20230528/ff38b104fe354c138f2305efb36dd34c.png
[format_png 4]: /images/20230528/0f89da9f83ee49899ff9518c920a3bd1.png