数组中的峰值元素

Question

所以我试图解决以下问题：

给定一个整数数组。找到其中的峰值元素。如果数组元素不小于其相邻元素，则该元素为峰值。对于角元素，我们只需要考虑一个邻居。例如，对于输入数组{5，10，20，15}，20是唯一的峰值元素。对于输入数组{10、20、15、2、23、90、67}，有两个峰值元素：20和90。请注意，我们需要返回任何一个峰值元素。

从以下链接：http://www.geeksforgeeks.org/find-a-peak-in-a-given-array/

有一次他们说

如果中间元素小于其左邻居，则在左半部分总是有一个峰值。

我在这一点上感到困惑，我们如何确定在左半部分会有一个峰值元素？我能从中得出的结论是，至少有1个元素肯定比它的右邻居（即a[m-1]）大，所以有可能是峰值元素。我已经研究了stackoverflow和其他站点，但无法找到对上述结论的良好解释

谢谢你的帮助！

Answer 1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @author asharda
 *
 */
public class Peak {

  public int findPeakElement(int[] nums) {

    Integer[] num = new Integer[nums.length];
    for (int i = 0; i < nums.length; i++) {
      num[i] = Integer.valueOf(nums[i]);
    }
    ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(num));
    Collections.sort(list);
    int peak = list.get(list.size() - 1);
    int top = 0;
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] == peak) {
        top = i;
      }
    }

    return top;
  }

  public static void main(String[] args) {

    int nums[] = {1, 2, 1, 3, 5, 6, 4};
    Peak p = new Peak();
    System.out.println(p.findPeakElement(nums));

  }

}

Answer 2

这句话很重要：

对于角元素，我们只需要考虑一个邻居。

让我们看看从中间元素向左迭代时会发生什么。我们知道左边的那个更大。如果它左边的一个更小或相等，那么你会发现一个峰值。如果不是，则递归。

这种递归有两种可能性：要么你最终找到一个峰值，要么你到达终点。如果你到达终点，那么末端的元素是你迄今为止找到的最大的元素，因此根据角落元素的定义，它是一个峰值。

Answer 3

假设您站在一个中间元素上，该元素低于其左邻居：

            element
                         you
                       element

你往左边看。它看起来像一座山。

假设你爬那座山。你看到了什么？有三种可能性：

1.
  element
              you
            element

                       element

2.
              you
  element   element

                       element

3.
              you
            element

  element              element

在第二种和第三种情况下，万岁！你找到了一个顶峰。在第一种情况下，你继续攀升。最终，要么你看到一个不高于你的元素，要么你撞上了左边的墙。在任何一种情况下，你都找到了一个顶峰。