C 语言数组中的峰值元素

在数组中，峰值元素是其不小于其邻居的元素。这是面试中经常被问到的问题之一。它很简单。本教程展示了我们可以遵循的不同方法来有效解决问题。

示例

假设数组为 [10, 20, 15, 23, 14]

23 是峰值元素，因为它不小于其两个邻居 - 15 和 14。

• 如果给定的输入数组按升序排序，则最后一个元素将是峰值元素。
• 如果数组按降序排序，则第一个元素将是峰值元素。如果数组中所有元素都相等，则所有元素都是峰值元素。
• 这证实了每个数组中总是至少有一个峰值元素。

朴素方法 #1：遍历整个数组

算法

1. 检查数组的第一个元素是否大于第二个元素。如果是，则返回 0。
2. 检查数组的最后一个元素是否大于倒数第二个元素。如果是，则返回 n-1。
3. 遍历数组中从索引 1 到 n-1 的整数 i，并检查 arr[i] > arr[i - 1] 且 arr[i] < arr[i + 1]。如果是，则返回 i。

代码

输出

Enter the size of the Array: 5
Enter the elements: 8 2 3 9 5
The first Peak element index in the Array: 0

时间复杂度：O(n) => 一次遍历

朴素方法 #2：查找数组中的最大元素

如果我们找到数组中的最大元素，那么它的邻居会自动小于该元素。我们可以在数组上使用 max() 函数。

算法

1. 使用两个变量，max = arr[0] 和 maxindex = 0
2. 从数组的第二个元素开始迭代整数 i，并持续检查 arr[i] > max。如果是，则更新 max = arr[i] 和 maxindex = i 的值。
3. 最后，返回 maxindex。

代码

输出

Enter size of the Array: 5
Enter the elements: 8 2 3 9 5
Peak element index in the Array: 3

时间复杂度：O(n) -> 一次遍历

高效方法

我们上面看到，找到最大元素可以得到一个峰值元素。所有时间都花在遍历整个数组，找到所有元素的最大值。我们可以将数组分成更小的部分，并在这些部分中找到峰值元素。

因此，我们使用“分治”方法。我们将遵循二分查找的算法。

算法

1. 初始化 l = 0 和 h = n - 1。找到中间元素：mid = l + (h - l) / 2。
2. 检查中间元素是否为峰值。如果是，则返回它。
3. 检查中间元素左侧的元素是否大于中间元素。如果是，则更新 h = mid - 1。
4. 检查中间元素右侧的元素是否大于中间元素。如果是，则更新 l = mid + 1。

代码

输出

Enter size of the Array: 5
Enter the elements: 8 2 3 9 5
Peak element index in the Array: 3

时间复杂度：O(Logn) -> 每一步，数组分成两半 -> 二分查找

迭代方法中的相同代码

为什么我们必须在不使用递归的情况下使用这种方法？两个代码是相同的，但是当我们使用递归时，会使用一个隐式堆栈来跟踪递归调用；我们可以通过使用循环来消除它。因此，使用这种方法时，时间复杂度没有改变，但空间复杂度变为常数。

代码

输出

Enter size of the Array: 5
Enter the elements: 8 2 3 9 5
Peak element index in the Array: 3