Algorithm

求一个数组的波峰

三个月前有人问我一道有趣的算法题，当时想了很久才想出来，现在写篇博客记录一下。

给定一个很长的数组 arr，已知数组长度为 length 且 length >= 3，数组的第一个元素不比第二个元素大，最后一个元素不比倒数第二个元素大。求这个数组中 任意一个 波峰的数组下标。PS：不比前一个元素小且不比后一个元素小的元素称为波峰。

既然 arr[1] >= arr[0]，那么只要再满足 arr[1] >= arr[2]，下标 1 就是一个波峰。

如果 arr[1] < arr[2]，那么只要 arr[2] >= arr[3]，下标 2 就是一个波峰。

……

这其实可以抽象成一个动态规划问题，但没必要；而且很明显，抽象之后还是得遍历……

等等……如果除去第一个元素和最后一个元素后，剩下的数组是有序递增的怎么办？这种情况下我们需要扫遍整个数组，从而付出 O(N) 的复杂度。有没有觉得这有点像连环诈骗：指针每次移动到的元素都满足波峰的前一部分条件（不比前一个元素小），我们满心欢喜地期待它满足下半部分条件，但有时并不能如愿。

有没有那么一瞬间想到二分搜索？

确实，这很像二分搜索能解决的问题。但是 数组并没有说明自己有序啊，所以根本不满足二分搜索的基本条件。

死马当活马医试试？

好吧，那我们试一下。先在数组的正中间取一个元素，记为 arr[length/2]。
取到之后，我们是不是应该满怀希望地迫不及待地将它和它的左右两个元素进行比较呢？因为这个比较发生在数组上，所以开销可以忽略不计。
如果它比左右都大，那很明显它就是一个波峰，此时返回它的下标 length/2 就可以了。
那如果它比左边小、比右边小，或者比左右都小呢？
那么波峰是不是可以在左边或者右边找一找？又如何确定左边或者右边一定有波峰呢？

这时，我们应该注意到两个问题。

  1. 如果它比左边小，那么 arr[:length/2+1] 这个子数组也符合题设条件；如果它比右边小，那么 arr[length/2:] 这个子数组也符合题设条件。
  2. 在左边找或者在右边找，一定能找到一个波峰吗？换句话说，符合题设条件的数组是否一定存在至少一个波峰？

如果把这两个问题想清楚，那么这道题就迎刃而解了。
给出示例代码（纯手写……）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_peak(arr, length):
    if length < 3:
        return -1

    middle = length / 2
    if length < 4:
        return middle 
    
    if arr[middle] > arr[middle - 1] and arr[middle] > arr[middle + 1]:
        return middle
    if arr[middle] < arr[middle - 1]:
        return find_peak(arr[:middle + 1], middle + 1)
    sub_length = middle + 1
    if length % 2 == 0:
        sub_length = middle
    return find_peak(arr[middle:], sub_length)

这个实现需要考虑很多边界情况，也许我的代码还没覆盖到；如果有问题，欢迎拍砖。

Share