Java 山峰索引问题

这是许多顶级 IT 公司（如谷歌、亚马逊、TCS、Accenture、Adobe、Apple、Infosys等）面试中经常出现的非常有趣的问题。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将通过不同的方法和逻辑来找出Java 中的山脉数组峰值索引。我们还将为之创建 Java 程序。

问题陈述

当一个数组满足以下条件时，它被称为山脉数组：

1. 给定数组的长度应大于或等于 3，即长度 >= 3。
2. 数组中必须只有一个峰值，即数组中的最大元素。
3. 数组必须满足条件：ARRAY[0] < ARRAY[1] < ARRAY[i-1] < ARRAY[ i] > ARRAY[ i+1 ] > ARRAY[..] > ARRAY[length-1]

任务是找出山脉数组的峰值索引。

假设给定的输入是 [60, 20, 90, 110, 10]。

输出将是 3。因为数组中最大的元素是 110，其索引是 3。

问题解决方案

可以使用以下两种方法解决此问题：

• 使用二分查找
• 使用线性查找

让我们逐一讨论上述方法。

使用二分查找

给定数组中的元素必须是升序或降序排列的。不应有重复元素。使用二分查找算法，我们可以找出所需的元素。在此方法中，每一步都将搜索范围减半。该问题可以通过以下步骤解决：

1. 找到数组 arr 的中间元素。
2. 如果数组按降序排列 (arr[mid] > arr[mid+1])，则意味着峰值元素将位于中间元素的左侧。因此，将搜索范围缩小到左半部分和中间。
3. 如果数组按升序排列 (arr[mid+1] < arr[mid])，则意味着峰值元素将位于中间元素的右侧。因此，将搜索范围缩小到右侧元素和中间+1。
4. 重复步骤 2 和 3，直到条件 left < right 不再成立。
5. 当条件 left >= right 成立时，峰值元素将位于左侧索引。

示例

假设输入数组是 {4, 2, 7, 9, 8, 3, 1}。

数组的长度是数组长度-1，即 7-1 = 6。

因此，High=6 且 Low=0。

让我们找到数组的中间值。

Mid=low+(high-low)/2

Mid=0+(6-0)/2 = 3

现在检查 (array[mid]>=array[mid+1]) 是否成立。

因此，9 >= 8，条件成立。将 high=Mid。

现在，low=0, Mid=3, High=3。

再次找到数组的中间值。Mid=low+(high-low)/2

Mid = 0 + (3 - 0) / 2 = 1

现在检查 (array[mid]>=array[mid+1])。

因此，2 >= 7，条件不成立。将 low=Mid+1。

现在，low=1+1=2, Mid=1, High=3。

再次找到数组的中间值。Mid=low+(high-low)/2

Mid = 2 + (3 - 2) / 2 = 2

现在检查 (array[mid]>=array[mid+1])。

因此，7 >= 9，条件不成立。将 low=Mid+1。

现在，low=2+1=3, Mid=2, High=3。

再次找到数组的中间值。Mid=low+(high-low)/2

Mid = 3 + (3 - 3) / 2 = 1

现在检查 (array[mid]>=array[mid+1])。

因此，2 >= 7，条件不成立。将 low=Mid+1。

重复上述过程。最后我们得到 low=3, High=3, Mid=3；

当进入循环 while (low < high) 时，即 3 < 3，条件变为 false。退出循环并返回 low，即 3。因此，峰值索引变为 3。

算法

1. 设置 low = 0。
2. 设置 high 为数组长度 - 1。
3. 声明一个变量 mid。
4. 设置 mid = low + (high - low) / 2。
5. 当 low < high 时
   1. 如果 array[ mid ] >= array [ mid + 1]。
      1. 则 high = mid。
   2. 否则
      1. 则 low = mid + 1。
   3. 返回 low。

让我们在 Java 程序中实现上述算法。

查找山脉数组峰值索引的 Java 程序

在此方法中，我们将使用二分查找。我们定义了一个名为 findPeakIndex() 的函数，在该函数中我们传入了输入数组和数组的长度。我们声明了一个名为 mid 的变量并将其初始化为 0，以及一个名为 high 的变量，它等于 high-1。在 while 循环中，我们定义了一个条件 low < high。该条件将一直执行，直到返回 false。进入循环后，我们设置 mid=low+(high-low) / 2。

GetPeakIndex.java

输出

The peak index of the mountain array is: 3

使用线性查找

在此方法中，我们遍历给定的输入数组 A。在每次迭代中，如果当前元素大于前一个元素并且当前元素小于下一个元素，则当前元素就是峰值元素。

让我们在 Java 程序中实现上述方法。

PeakIndex.java

输出

The peak index of the mountain array is: 4

复杂度

上述解决方案的时间复杂度为 O(log n)，其中 n 是数组的长度。空间复杂度为 O(1)，因为我们没有使用任何额外的空间进行计算。