在山脉数组中查找元素Leetcode162,Leetcode 852,Leetcode1095和Leetcode941

一、在山脉数组中查找峰值元素

典型的题目有：Leetcode 162. 寻找峰值和 Leetcode 852. 山脉数组的峰顶索引，都是要找出数组中峰值元素的索引。峰值元素的取值比它两边的元素要大，就像山峰的峰顶一样，因此这种数组也被称为山脉数组。

题目要求使用代码的时间复杂度是 O(log n)，我们首先想到用二分查找法。可是，数组的元素有起伏变化，还能用二分查找吗？仔细观察会发现，其实峰值的两侧都是有规律地变化：单调递增或递减。Leetcode 852 的数组中只有一个峰值元素。而 Leetcode 162 的数组可能有多个峰值元素，可以把元素的取值变化想象成相邻的多个小山坡，或者波浪型，两个峰值之间的元素也分段符合单调递增或递减规律，因此可以采用相同的思路。

用二分查找解决这类问题的关键点：不是寻找一个确定值 target，而是寻找一个有峰值特征的元素，也就是这个元素比两边元素的值要大。只要修改二分查找中对 middle 元素的判断条件如下：

如果 middle 元素比两边元素都大（ nums[middle] > nums[middle - 1] 并且 nums[middle] > nums[middle + 1]），这就是我们要找的峰值元素，返回 middle。
如果不符合上述条件，说明 middle 元素处于山腰上，怎么到山顶呢？往高处（数值大的元素所在区间）走。
- 如果 nums[middle] < nums[middle - 1] ，接着在 [ left, middle - 1 ] 区间内寻找。
- 如果 nums[middle] < nums[middle + 1] ，接着在 [ middle + 1, right ] 区间内寻找。

细节：数组首尾元素。这个方法应用于数组首尾元素，例如 middle = length(nums) - 1 时，nums[middle +1] 超出索引范围，会报错。因此，搜索区间初始为 [ 1, length -2 ]。而判断是否为峰值元素时，区间要有至少 3 个元素： arr[mid-1] < arr[mid] < arr[mid+1]，因此，应用二分查找时数组长度不小于 3。

这里以 Leetcode 852 为例，其代码为：

class Solution:def peakIndexInMountainArray(self, arr: List[int]) -> int:low, high = 1, len(arr) - 2while low <= high:mid = low + (high - low) // 2if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:return midelif arr[mid] < arr[mid + 1]:low = mid + 1elif arr[mid] < arr[mid - 1]:high = mid - 1return low

Leetcode 162 给定的数组长度不小于 1，需要在上述代码之前加上对于数组长度小于 3 时的处理。此外，这道题假设 nums[-1] = nums[n] = -∞，数组首尾元素也有可能是峰值元素，需要额外考虑。具体代码为：

# 数组长度为 1，直接返回该元素
if len(nums) == 1:return 0
# 查看数组首尾元素是否是峰值元素
if nums[0] > nums[1]:return 0
if nums[-1] > nums[-2]:return len(nums) - 1

二、在山脉数组中查找目标值

Leetcode 1095. 山脉数组中查找目标值这道题基于 Leetcode 852 ，但更难一些，还要在数组中寻找一个目标值。因为这个数组是山脉数组，如果目标值出现了两次，题目要求返回较小的索引值。

解题的关键在于要先找到峰值元素，以该元素为界把整个数组划分成递增数组和递减数组。 接下来就容易了，只要先在峰值元素的左区间、再在右区间应用二分查找寻找目标值。先查找左区间、再查找右区间是为了返回符合条件的较小索引。总体要做 3 次二分查找。

当我理解了这道题的解题思路之后，就用 Leetcode 852 的方法寻找峰值。但是代码运行报错：调用 MountainArray.get(k) 函数超过了 100 次限制。我看了这个解答，发现如果用 while low < high，判断条件会简化，因此调用 MountainArray.get(k) 函数次数也会减少。相应的代码及注释如下：

length = mountain_arr.length()low, high = 1, length - 2
while low < high:mid = low + (high - low) // 2# 这种情况下与之前的处理相同if mountain_arr.get(mid) < mountain_arr.get(mid + 1):low = mid + 1# 变化在这里：arr[mid]>arr[mid+1]时# 把 arr[mid]>arr[mid-1] 和 arr[mid]<arr[mid-1] 两种情况合并# 此时有边界应包含 mid（考虑到arr[mid]>arr[mid-1]时mid符合条件）else:high = mid 
# 搜索区间只剩一个元素，就是峰值元素
peak = low

注：我用此方法再做一遍 Leetcode 852 ，发现它比前面使用的 while low <= high 方法更快，可能是简化了判断条件带来的提升。

回到本题Leetcode 1095，找到峰值之后，后面就用基本二分查找法先在峰值的左区间 [ 0, peak ]，后在峰值的右区间 [ peak+1, length-1 ]寻找就好了。这一步比较简单，就不列出具体代码了。需要注意的是峰值的右区间是单调递减数组，与我们经常遇到的递增数组在左右区间选择上不同。比如，mid 元素值小于目标值时，mid 元素左边的元素比它大，因此应该到左区间继续寻找。同理，mid 元素值大于目标值时，则应该到右区间继续寻找。

三、有效的山脉数组

之前分析的两种情况都是在山脉数组中寻找某个元素，主要用到二分查找法。而接下来的这道题 Leetcode 941. 有效的山脉数组是要判断一个数组是不是有效的山脉数组，即满足：（1）数组长度不小于 3。（2）存在一个元素（峰值元素），该元素左边元素单调递增，该元素右边元素单调递减。

设想一下，如果两人爬的是同一座山，分别从左右两侧的山底开始走，那么最终会在山顶相遇。这个思路也可以用在这道题的解答中，为此我们需要用到双指针。相应的代码及注释如下：

class Solution:def validMountainArray(self, arr: List[int]) -> bool:length = len(arr)# 判断条件(1)：山脉数组的长度不小于3if length < 3:return False# 左、右指针分别指向数组的首尾元素left, right= 0, length - 1# 左指针往山顶方向移动：# 山顶元素左右两边都有元素，因此其索引在[1,length-2]范围# 如果左指针右边相邻的元素值更大，依次增大索引，直到不满足条件while left + 1 < length - 1 and arr[left + 1] > arr[left]:left += 1# 右指针往山顶方向移动：# 如果右指针左边相邻的元素值更大，依次减小索引，直到不满足条件while right - 1 > 0 and arr[right - 1] > arr[right]:right -= 1# 此时左右指针都指向了某个峰值元素，也就是爬到了某个山顶# 判断条件(2)：山脉数组只有一个山顶，左右指针指向的是同一个山顶吗？if left == right:return Trueelse:return False

参考

Leetcode 162 思路：Intuition behind conditions
Leetcode 1095 思路：[Java/C++/Python] Triple Binary Search - Find in Mountain Array - LeetCode
Leetcode 941 思路：[C++/Java/Python] Climb Mountain - Valid Mountain Array - LeetCode