深入解析力扣162题：寻找峰值（线性扫描与二分查找详解）

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

• 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
  

• 导航：

  • LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
  • 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
  • python源码解读：解读python的源代码与调用关系，快速提升代码质量
  • python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
  • 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

在本篇文章中，我们将详细解读力扣第162题“寻找峰值”。通过学习本篇文章，读者将掌握如何使用多种方法来解决这一问题，并了解相关的复杂度分析。每种方法都将配以详细的解释和ASCII图解，以便于理解。

问题描述

力扣第162题“寻找峰值”描述如下：

峰值元素是指其值大于左右相邻值的元素。给你一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

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

示例 2:

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

解题思路

1. 初步分析：
   • 峰值元素是指其值大于左右相邻值的元素。
   • 可以使用线性扫描的方法找到峰值，也可以使用二分查找来提高效率。

方法一：线性扫描

1. 步骤：
   • 遍历数组中的每个元素，检查其是否大于左右相邻的元素。
   • 返回第一个满足条件的元素索引。

代码实现

def findPeakElement(nums):
    for i in range(len(nums)):
        if (i == 0 or nums[i] > nums[i - 1]) and (i == len(nums) - 1 or nums[i] > nums[i + 1]):
            return i
    return -1

# 测试案例
print(findPeakElement([1, 2, 3, 1]))  # 输出: 2
print(findPeakElement([1, 2, 1, 3, 5, 6, 4]))  # 输出: 1 或 5
1
2
3
4
5
6
7
8
9

ASCII图解

假设输入数组为 [1, 2, 3, 1]，图解如下：

数组: [1, 2, 3, 1]

遍历过程:
i = 0, nums[i] = 1 (不是峰值)
i = 1, nums[i] = 2 (不是峰值)
i = 2, nums[i] = 3 (是峰值)

返回索引 2
1
2
3
4
5
6
7
8

方法二：二分查找

1. 步骤：
   • 使用二分查找的方法，在每次查找过程中比较中间元素与其相邻元素的大小。
   • 根据比较结果缩小查找范围，直到找到峰值元素。

代码实现

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    
    return left

# 测试案例
print(findPeakElement([1, 2, 3, 1]))  # 输出: 2
print(findPeakElement([1, 2, 1, 3, 5, 6, 4]))  # 输出: 1 或 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ASCII图解

假设输入数组为 [1, 2, 3, 1]，图解如下：

数组: [1, 2, 3, 1]

初始状态: left = 0, right = 3

第一次二分查找:
mid = (0 + 3) // 2 = 1
nums[mid] = 2, nums[mid + 1] = 3
nums[mid] < nums[mid + 1]
left = mid + 1 = 2

第二次二分查找:
mid = (2 + 3) // 2 = 2
nums[mid] = 3, nums[mid + 1] = 1
nums[mid] > nums[mid + 1]
right = mid = 2

最终状态: left = 2, right = 2

返回索引 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析

• 时间复杂度：
  • 线性扫描法：O(n)，其中 n 是数组的长度。
  • 二分查找法：O(log n)，其中 n 是数组的长度。
• 空间复杂度：
  • 两种方法均为 O(1)，只使用了常数空间来存储计数变量和索引。

测试案例分析

1. 测试案例 1：

   • 输入: nums = [1, 2, 3, 1]
   • 输出: 2
   • 解释: 3 是峰值元素，返回索引 2。

2. 测试案例 2：

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

总结

本文详细解读了力扣第162题“寻找峰值”，通过线性扫描法和二分查找法两种方法，高效地解决了这一问题。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。

参考资料

• 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• 力扣官方题解

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/750637