1. Introduction
1.导言
Peak elements within an array are important for numerous algorithms, offering valuable insights into the dataset’s characteristics. In this tutorial, let’s explore the concept of peak elements, explaining their significance and exploring efficient methods to identify them, both in single and multiple peak scenarios.
数组中的峰值元素对许多算法都很重要，能为数据集的特征提供有价值的见解。在本教程中，我们将探讨峰值元素的概念，解释其重要性，并探索在单峰值和多峰值情况下识别峰值元素的有效方法。
2. What is a Peak Element?
2.什么是峰值元素？
A peak element in an array is defined as an element that is strictly greater than its adjacent elements. Edge elements are considered to be in a peak position if they are greater than their only neighboring element.
数组中的峰值元素定义为严格大于其相邻元素的元素。如果边缘元素大于其唯一相邻元素，则被认为处于峰值位置。
In scenarios where elements are equal, a strict peak does not exist. Instead, a peak is the first instance where an element exceeds its neighbors.
在元素相等的情况下，不存在严格意义上的峰值。相反，峰值是一个元素超过其邻近元素的第一个实例。
2.1. Examples
2.1.实例
To better understand the idea of peak elements, take a look at the following examples:
为了更好地理解峰值元素的概念，请看下面的例子：
Example 1:
<强>示例 1：</强
List: [1, 2, 20, 3, 1, 0]
Peak Element: 20Here, 20 is a peak since it is greater than its neighboring elements.
在这里，20 是一个峰值，因为它大于相邻的元素。
Example 2:
<强>示例 2：</强
List: [5, 13, 15, 25, 40, 75, 100]
Peak Element: 100100 is a peak because it’s greater than 75 and has no element to its right.
100 是一个峰值，因为它大于 75，而且右边没有元素。
Example 3:
例 3：
List: [9, 30, 13, 2, 23, 104, 67, 12]
Peak Element: 30 or 104, as both are valid peaksBoth 30 and 104 qualify as peaks.
30 和 104 都属于峰值。
3. Finding Single Peak Elements
3.寻找单峰元素
When an array contains only one peak element, a straightforward approach is to utilize linear search. This algorithm scans through the array elements, comparing each with its neighbors until finding a peak. The time complexity of this method is O(n), where n is the size of the array.
当数组只包含一个峰值元素时，一种直接的方法是 使用线性搜索。这种算法会扫描数组元素，将每个元素与其相邻元素进行比较，直到找到一个峰值。这种方法的时间复杂度为 O(n)，其中 n 是数组的大小。
public class SinglePeakFinder {
public static OptionalInt findSinglePeak(int[] arr) {
int n = arr.length;
if (n < 2) {
return n == 0 ? OptionalInt.empty() : OptionalInt.of(arr[0]);
}
if (arr[0] >= arr[1]) {
return OptionalInt.of(arr[0]);
}
for (int i = 1; i < n - 1; i++) {
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) {
return OptionalInt.of(arr[i]);
}
}
if (arr[n - 1] >= arr[n - 2]) {
return OptionalInt.of(arr[n - 1]);
}
return OptionalInt.empty();
}
}The algorithm iterates through the array from index 1 to n-2, checking if the current element is greater than its neighbors. If a peak is found, an OptionalInt containing the peak is returned. Additionally, the algorithm handles edge cases where the peak is at the extremes of the array.
该算法从索引 1 到 n-2 依次遍历数组，检查当前元素是否大于其相邻元素。如果发现峰值，则返回一个包含峰值的 OptionalInt 。此外，该算法还能处理峰值位于数组极值的边缘情况。
public class SinglePeakFinderUnitTest {
@Test
void findSinglePeak_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeak() {
int[] arr = {0, 10, 2, 4, 5, 1};
OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
assertTrue(peak.isPresent());
assertEquals(10, peak.getAsInt());
}
@Test
void findSinglePeak_givenEmptyArray_thenReturnsEmptyOptional() {
int[] arr = {};
OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
assertTrue(peak.isEmpty());
}
@Test
void findSinglePeak_givenEqualElementArray_thenReturnsCorrectPeak() {
int[] arr = {-2, -2, -2, -2, -2};
OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
assertTrue(peak.isPresent());
assertEquals(-2, peak.getAsInt());
}
}In the case of bitonic arrays—characterized by a monotonically increasing sequence followed by a monotonically decreasing sequence—the peak can be found more efficiently. By applying a modified binary search technique, we can locate the peak in O(log n) time, significantly reducing the complexity.
位子数组的特征是单调递增序列紧随单调递减序列，在这种情况下，可以更高效地找到峰值。通过应用改进的二进制搜索技术，我们可以在O(log n)时间内找到峰值，大大降低了复杂性。
It’s important to note that determining whether an array is bitonic requires examination, which, in the worst case, can approach linear time. Therefore, the efficiency gain with the binary search approach is most impactful when the array’s bitonic nature is known.
值得注意的是，确定数组是否是位子数组需要进行检查，在最坏的情况下，检查时间可能接近线性时间。因此，二进制搜索方法在已知数组的位子性质时最能提高效率。
4. Finding Multiple Peak Elements
4.寻找多个峰值元素
Identifying multiple peak elements in an array typically requires examining each element in relation to its neighbors, leading to a linear search algorithm with a time complexity of O(n). This approach ensures no potential peak is overlooked, making it suitable for general arrays.
要识别数组中的多个峰值元素，通常需要检查每个元素与其相邻元素的关系，这就导致了一种线性搜索算法，其时间复杂度为O(n)。这种方法确保不会忽略任何潜在的峰值，因此适用于一般数组。
In specific scenarios, when the array structure allows for segmenting into predictable patterns, modified binary search techniques can be applied to find peaks more efficiently. Let’s use a modified binary search algorithm to achieve a time complexity of O(log n).
在特定情况下，当数组结构允许分割成可预测的模式时，可以采用改进的二进制搜索技术来更高效地找到峰值。让我们使用改进的二进制搜索算法来实现 O(log n) 的时间复杂度。
Algorithm Explanation:
算法说明：
- Initialize Pointers: Start with two pointers, low and high, representing the range of the array.
- Binary Search: Calculate the middle index mid of the current range.
- Compare Mid with Neighbors: Check if the element at index mid is greater than its neighbors.
- If true, mid is a peak.
- If false, move towards the side with the greater neighbor, ensuring we move towards a potential peak.
- Repeat: Continue the process until the range is reduced to a single element.
public class MultiplePeakFinder {
public static List<Integer> findPeaks(int[] arr) {
List<Integer> peaks = new ArrayList<>();
if (arr == null || arr.length == 0) {
return peaks;
}
findPeakElements(arr, 0, arr.length - 1, peaks, arr.length);
return peaks;
}
private static void findPeakElements(int[] arr, int low, int high, List<Integer> peaks, int length) {
if (low > high) {
return;
}
int mid = low + (high - low) / 2;
boolean isPeak = (mid == 0 || arr[mid] > arr[mid - 1]) && (mid == length - 1 || arr[mid] > arr[mid + 1]);
boolean isFirstInSequence = mid > 0 && arr[mid] == arr[mid - 1] && arr[mid] > arr[mid + 1];
if (isPeak || isFirstInSequence) {
if (!peaks.contains(arr[mid])) {
peaks.add(arr[mid]);
}
}
findPeakElements(arr, low, mid - 1, peaks, length);
findPeakElements(arr, mid + 1, high, peaks, length);
}
}The MultiplePeakFinder class employs a modified binary search algorithm to identify multiple peak elements in an array efficiently. The findPeaks method initializes two pointers, low and high, representing the range of the array.
MultiplePeakFinder 类采用了一种改进的二进制搜索算法，可以高效地识别数组中的多个峰值元素。findPeaks方法初始化了两个指针low和high，它们代表了数组的范围。
It calculates the middle index (mid) and checks if the element at mid is greater than its neighbors. If true, it marks mid as a peak and continues the search in the potential peak-rich region.
它会计算中间索引（mid），并检查 mid 处的元素是否大于其邻近元素。如果true，它就会将mid标记为峰值，并继续在潜在的峰值丰富区域进行搜索。
public class MultiplePeakFinderUnitTest {
@Test
void findPeaks_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeaks() {
MultiplePeakFinder finder = new MultiplePeakFinder();
int[] array = {1, 13, 7, 0, 4, 1, 4, 45, 50};
List<Integer> peaks = finder.findPeaks(array);
assertEquals(3, peaks.size());
assertTrue(peaks.contains(4));
assertTrue(peaks.contains(13));
assertTrue(peaks.contains(50));
}
}
The efficiency of binary search for finding peaks depends on the array’s structure, allowing for peak detection without checking every element. However, without knowing the array’s structure or if it lacks a suitable pattern for binary search, linear search is the most dependable method, guaranteeing no peak is overlooked.
二进制搜索寻找峰值的效率取决于数组的结构，它可以在不检查每个元素的情况下进行峰值检测。但是，如果不知道数组的结构，或者数组缺乏适合二进制搜索的模式，线性搜索就是最可靠的方法，它可以保证峰值不会被忽略。
5. Handling Edge Cases
5.处理边缘案例
Understanding and addressing edge cases is crucial for ensuring the robustness and reliability of the peak element algorithm.
了解和处理边缘情况对于确保峰值元素算法的稳健性和可靠性至关重要。
5.1. Array With No Peaks
5.1.无峰值阵列
In scenarios where the array contains no peak elements, it is essential to indicate this absence. Let’s return an empty array when no peaks are found:
在数组不包含峰值元素的情况下，必须指出这种缺失。当没有发现峰值时，让我们返回一个空数组：
public class PeakElementFinder {
public List<Integer> findPeakElements(int[] arr) {
int n = arr.length;
List<Integer> peaks = new ArrayList<>();
if (n == 0) {
return peaks;
}
for (int i = 0; i < n; i++) {
if (isPeak(arr, i, n)) {
peaks.add(arr[i]);
}
}
return peaks;
}
private boolean isPeak(int[] arr, int index, int n) {
return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
}
}The findPeakElement method iterates through the array, utilizing the isPeak helper function to identify peaks. If no peaks are found, it returns an empty array.
findPeakElement 方法遍历数组，利用 isPeak 辅助函数识别峰值。如果没有找到峰值，则返回空数组。
public class PeakElementFinderUnitTest {
@Test
void findPeakElement_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeak() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {1, 2, 3, 2, 1};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(1, peaks.size());
assertTrue(peaks.contains(3));
}
@Test
void findPeakElement_givenArrayOfIntegers_whenNoPeaks_thenReturnsEmptyList() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(0, peaks.size());
}
}5.2. Array With Peaks at Extremes
5.2.极值处有峰值的阵列
When peaks exist at the first or last element, special consideration is necessary to avoid undefined neighbor comparisons. Let’s add a conditional check in the isPeak method to handle these cases:
当峰值存在于第一个或最后一个元素时，需要特别考虑以避免未定义的邻接比较。让我们在 isPeak 方法中添加 条件检查，以处理这些情况：
private boolean isPeak(int[] arr, int index, int n) {
if (index == 0) {
return n > 1 ? arr[index] >= arr[index + 1] : true;
} else if (index == n - 1) {
return arr[index] >= arr[index - 1];
}
return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
}
This modification ensures that peaks at the extremes are correctly identified without attempting comparisons with undefined neighbors.
这一修改可确保正确识别极值峰，而无需尝试与未定义的邻近峰进行比较。
public class PeakElementFinderUnitTest {
@Test
void findPeakElement_givenArrayOfIntegers_whenPeaksAtExtremes_thenReturnsCorrectPeak() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {5, 2, 1, 3, 4};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(2, peaks.size());
assertTrue(peaks.contains(5));
assertTrue(peaks.contains(4));
}
}5.3. Dealing With Plateaus (Consecutive Equal Elements)
5.3.处理高原（连续等元素）
In cases where the array contains consecutive equal elements, returning the index of the first occurrence is crucial. The isPeak function handles this by skipping consecutive equal elements:
在数组包含连续相等元素的情况下，返回第一次出现的索引至关重要。isPeak函数通过跳过连续相等元素来处理这种情况：
private boolean isPeak(int[] arr, int index, int n) {
if (index == 0) {
return n > 1 ? arr[index] >= arr[index + 1] : true;
} else if (index == n - 1) {
return arr[index] >= arr[index - 1];
} else if (arr[index] == arr[index + 1] && arr[index] > arr[index - 1]) {
int i = index;
while (i < n - 1 && arr[i] == arr[i + 1]) {
i++;
}
return i == n - 1 || arr[i] > arr[i + 1];
} else {
return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
}
}The findPeakElement function skips consecutive equal elements, ensuring that the index of the first occurrence is returned when identifying peaks.
findPeakElement函数会跳过连续的相等元素，确保在识别峰值时返回第一次出现的索引。
public class PeakElementFinderUnitTest {
@Test
void findPeakElement_givenArrayOfIntegers_whenPlateaus_thenReturnsCorrectPeak() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {1, 2, 2, 2, 3, 4, 5};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(1, peaks.size());
assertTrue(peaks.contains(5));
}
}6. Conclusion
6.结论
Understanding the techniques to find peak elements enables developers to make informed decisions when designing efficient and resilient algorithms. There are various approaches to discovering peak elements, with methods offering different time complexities, such as O(log n) or O(n).
了解了发现峰值元素的技术，开发人员就能在设计高效、弹性算法时做出明智的决策。有多种发现峰值元素的方法，这些方法提供了不同的时间复杂度，例如 O(log n) 或 O(n)。
The selection among these methods depends on specific requirements and application constraints. Choosing the right algorithm aligns with the efficiency and performance goals aimed to achieve in the application.
这些方法的选择取决于具体要求和应用限制。选择正确的算法与应用中要实现的效率和性能目标相一致。
You can find all the code samples over on GitHub.
您可以在 GitHub 上找到所有代码示例。