寻找给定数组的一维峰值

Question

我正在编写一个用于1D数组的峰值查找算法的代码。我阅读了这篇帖子Peak finding algorithm，这正是我想做的事情，讨论了时间复杂度，但没有伪代码。问题是：

给定一个数组[a,b,c,d,e,f,g]，其中a到g都是数字，如果且仅当a<=b和b>=c时，b是一个峰值。

例如：给定一个数组{1,2,3,4,5,19,25,20}，应该返回索引6。 边缘情况应该给出： {100,4,3,1,19,20} -- index 0 {1,3,5,19,20} -- index 4 我已经在Java中实现了代码，我的当前运行时间为O(n)。我想知道是否可以改进。

public static int naive(int[] arr){
        int l=arr.length;
        if (arr[0]>=arr[1]) {
            return 0;
        }
        if (arr[l-1]>arr[l-2]){
            return l-1;
        }
        for (int i=1; i < arr.length-1;i++){
             if (arr[i] >= arr[i-1] && arr[i] >= arr[i+1] ){
                 return i;
             }
        }
        return -1;
    }

- eagertoLearn

---

可以使用分治算法编码，这样可以获得O(log n)的时间复杂度。 - brain storm

@user1988876：那将如何工作，我需要遍历整个数组才能找到峰值。因此时间复杂度必须为O(n)。 - eagertoLearn

你感兴趣的是找到一个单峰，而不是所有的峰。 - brain storm

只是为了更好地理解，如果您有一个值为[5,5,5,7,2]的数组，您认为第二个5是峰值吗？ - George

@George：我猜两者都有。7 是全局峰值，但 5 和 7 是局部峰值。 - eagertoLearn

Answer 1

以下函数可能比你的函数更加高效。请注意，这将找到一个本地极值点。

    public static int findLocalMaximum(int[] arr){
        int i = 0;
        while(i + 1 < arr.length && arr[i+1] >= arr[i]) {
            ++i;
        }
        return i;
    }

编辑：以下函数根据问题定义查找峰值。请注意，我在 while 循环中删除了边界检查，因为只有当 arr[l-2] > arr[l-1] 时，该循环才会被执行，因此 while 循环中的条件将为 false，并返回 l-2。

    public static int findPeak(int[] arr){
        int l = arr.length;
        if(arr[0] >= arr[1]) {
            return 0;
        }

        if(arr[l-1] >= arr[l-2]) {
            return l-1;
        }

        int i = 1;
        while(arr[i+1] > arr[i]) {
            ++i;
        }
        return i;
    }

- George

Answer 2

如果我可以提出我的解决方案：

public static int findPeak(int[] array, int start, int end) {
    int index = start + (end - start) / 2;

    if (index - 1 >= 0 && array[index] < array[index - 1]) {
        return findPeak(array, start, index - 1);
    } else if (index + 1 <= array.length - 1 && array[index] < array[index + 1]) {
        return findPeak(array, index + 1, end);
    } else {
        return array[index];
    }
}

我认为在if语句中直接处理边缘情况更简单。我还尝试了几个输入，看起来运行良好。

- Remy Cilia

---

start + (end - start) / 2 可以简化为 (start + end) / 2。 - Roy Lee

@RoyLee，start + (end - start) / 2 可以避免溢出。 - adyavanapalli

Answer 3

一个类似于二分查找的算法应该可以解决问题，采用分而治之的策略。由于您对单峰感兴趣，因此最好的情况是O(log n)。但如果您想找到所有峰值，至少需要O(n)。以下是分而治之算法：

public static int peak1D(int[] arr, int start, int end){
          //edge cases
        if (end-start==1){
            if (start==0)
                return start;
            else 
             return end;
        }
        int i = start+end>>>1;
        if (arr[i]<arr[i-1])
           return peak1D(arr,start,i);
        if (arr[i]<arr[i+1]){
            return peak1D(arr, i, end);
        }
        else
            return i;
    }

我测试了几个输入，似乎它可以工作。我的边界处理不是很好。尽管这是简单的推理。

- brain storm

---

抱歉，我不确定那会不会有效。或许是我没有理解清楚。你能给我一个伪代码让我试一下吗？ - eagertoLearn

@eagertoLearn：请给我几分钟，我正在处理。 - brain storm

@Marichyasana：我说“二分查找类似”的时候，我的意思是“分而治之”。 - brain storm

@user1988876，请尝试使用 {3, 2, 1, 0, 5, 4}。但是不起作用。问题在于无法通过查看中间部分来确定顶部或底部的一侧是否存在局部峰值。要找到局部峰值，必须按顺序浏览整个数组，直到找到一个或到达末尾。 - gdejohn

这个算法之所以有效，是因为允许了边缘情况（arr[0]，arr[n-1]）。 - Bernd Elkemann

Answer 4

为简单起见，假设Array是全局的，如果需要，您可以将其传递。

    private static int getPeak1D(int start,int end)
{
    int x = (start+end)/2;

    if(     (x == 0 && array[x] >= array[x+1]) ||
            (x == array.length-1 && array[x]>=array[x-1]) ||
            (x>0 && x< array.length-1 && array[x] >= array[x-1] && array[x] >= array[x+1]))
        return x;

    if(x+1 < array.length && array[x] < array[x+1])
        temp =  getPeak1D(x+1,end);

    if(temp > -1)
        return temp;

    if(x-1 > -1 && array[x] < array[x-1])
        return getPeak1D(0,x-1);
    else
        return -1;
}

第一个if检查峰值的第一条边缘、第二条边缘和内部部分。 如果没有发现峰值，如果array[x+1] > array[x]，第二个if将进入数组的右半部分。我们将其存储在temp中（我将其作为全局变量），我们不返回它，因为如果array[x+1]和array[x-1]都比array[x]大，但右侧没有找到任何峰值，则应该转到第三个if以检查左侧。

查看此链接以了解其背后的逻辑https://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf

- Ayman H