图解LeetCode之寻找峰值（LeetCode 162题）

LeetCode 162题是一个比较有挑战性的题目，要求在给定数组中找到峰值元素并返回其索引。峰值元素是指其值大于左右相邻值的元素。下面我们将通过图解的方式详细解析这道题目。
首先，我们需要明确题目要求和解题思路。题目要求我们找到峰值元素并返回其索引，数组中每个元素都不相等，且数组的边界元素是负无穷。这意味着我们可以通过一次遍历找到峰值元素，而不需要额外的时间复杂度。
接下来，我们可以开始编写代码实现这个算法。我们可以使用双指针的方法来找到峰值元素。我们初始化两个指针left和right，分别指向数组的第一个元素和最后一个元素。然后，我们比较中间元素和其左侧、右侧元素的相对大小关系。
如果中间元素大于其左侧元素和右侧元素，那么它就是峰值元素，我们返回它的索引。否则，我们将指针left或right向中间靠拢，继续比较新的元素和其左右相邻元素的相对大小关系，直到找到峰值元素或者指针相遇为止。
以下是实现这个算法的Python代码：

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

现在我们来通过图解的方式解释这个算法的执行过程。假设输入数组为[1,2,3,1]，我们可以将其可视化表示为一个高度图：
[请在此处插入高度图]
根据题目要求，我们可以将数组的边界元素视为负无穷，因此在高度图中表示为-∞。然后，我们初始化两个指针left和right，分别指向第一个元素和最后一个元素。在高度图中，这两个指针分别位于1和3的位置。
接下来，我们进入while循环，计算中间元素的索引mid。在第一次循环中，mid=1，我们将1、2、3三个元素进行比较：

• nums[mid]=2，比nums[mid+1]=1大，比nums[mid-1]=1也大，所以2是峰值元素，我们返回mid=1作为结果。在高度图中表示为将指针从3移动到1的位置。
  如果输入数组为[1,2,1,3,5,6,4]，我们可以将其可视化表示为一个高度图：
  [请在此处插入高度图]
  初始化两个指针left和right后，我们进入while循环，计算中间元素的索引mid。在第一次循环中，mid=1，我们将1、2、1三个元素进行比较：
• nums[mid]=2，比nums[mid+1]=1大，比nums[mid-1]=1也大，所以2是峰值元素，我们返回mid=1作为结果。在高度图中表示为将指针从4移动到1的位置。
  如果输入数组为[3,2,1]，我们可以将其可视化表示为一个高度图：
  [请在此处插入高度图]
  初始化两个指针left和right后，我们进入while循环，计算中间元素的索引mid。在第一次循环中，mid=0，我们将3、2、1三个元素进行比较：
• nums[mid]=3，比nums[mid+1]=2大，比nums[mid-1]=1也大，所以3是峰值元素，我们返回mid=0作为结果。在高度图中表示为将指针从2移动到0的位置。
  总结：通过图解的方式解析LeetCode 162题，我们可以更好地理解题目要求和解题思路。使用双指针的方法可以在一次遍历中找到峰值元素，时间复杂度为O(logN)。在实现时需要注意指针的移动和边界情况的处理。