1. 引言
峰值元素在数组分析中扮演着重要角色，为理解数据集特征提供了关键信息。本文将深入探讨峰值元素的概念，解释其重要性，并介绍在单峰值和多峰值场景下的高效识别方法。
2. 什么是峰值元素？
峰值元素是指严格大于其相邻元素的数组元素。 对于边缘元素（首/尾元素），只需大于其唯一的相邻元素即可视为峰值。
当存在相等元素时，严格意义上的峰值不存在。此时，峰值定义为第一个超过其相邻元素的元素。
2.1. 示例
通过以下示例理解峰值元素的概念：
示例 1：
列表: [1, 2, 20, 3, 1, 0]
峰值元素: 20
20 是峰值，因为它大于左右相邻元素。
示例 2：
列表: [5, 13, 15, 25, 40, 75, 100]
峰值元素: 100
100 是峰值，因为它大于左侧的 75 且右侧无元素。
示例 3：
列表: [9, 30, 13, 2, 23, 104, 67, 12]
峰值元素: 30 或 104（两者均为有效峰值）
30 和 104 都满足峰值条件。
3. 寻找单峰值元素
当数组仅含一个峰值时，最简单粗暴的方法是线性搜索。该算法遍历数组，比较每个元素与其相邻元素，直到找到峰值。 时间复杂度为 *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();
}
}
算法遍历数组（索引 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());
}
}
对于双调数组（先单调递增后单调递减），可通过改进的二分查找技术更高效地找到峰值，时间复杂度降至 *O(log n)*。
⚠️ 注意：判断数组是否为双调本身可能需要线性时间，因此当已知数组具有双调特性时，二分查找的优势才能最大化。
4. 寻找多峰值元素
识别数组中的多个峰值通常需要检查每个元素与其相邻元素的关系，导致时间复杂度为 O(n) 的线性搜索。这种方法能确保不遗漏任何潜在峰值，适用于一般数组。
在特定场景下（如数组可分割为可预测模式），可通过改进的二分查找技术高效定位峰值。以下算法实现 O(log n) 时间复杂度：
算法步骤：
- 初始化指针： 设置指针 low 和 high 表示数组范围
- 二分查找： 计算当前范围的中点索引 mid
- 比较中点与相邻元素： 检查 mid 处元素是否大于相邻元素
- 若成立，mid 即为峰值
- 若不成立，向值更大的相邻元素方向移动（确保朝潜在峰值方向搜索）
- 重复： 持续此过程直至范围缩小至单个元素
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);
}
}
MultiplePeakFinder 类采用改进的二分查找算法高效识别多峰值。*findPeaks 方法初始化指针 low 和 high 表示数组范围，计算中点 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));
}
}
二分查找的效率取决于数组结构，可在不检查所有元素的情况下检测峰值。 但若未知数组结构或缺乏适合二分查找的模式，线性搜索仍是可靠选择，确保不遗漏任何峰值。
5. 处理边界情况
处理边界情况对确保峰值算法的鲁棒性至关重要。
5.1. 无峰值数组
当数组不含峰值时，需明确指示此情况。 以下实现返回空列表表示无峰值：
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];
}
}
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. 峰值位于边缘
当峰值位于首/尾元素时，需特殊处理以避免未定义的相邻元素比较。 在 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];
}
此修改确保正确识别边缘峰值，避免与未定义相邻元素比较。
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. 处理平台（连续相等元素）
当数组含连续相等元素时，应返回首个出现位置的索引。 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];
}
}
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. 总结
掌握寻找峰值元素的技术，能帮助开发者在设计高效鲁棒的算法时做出明智决策。存在多种发现峰值的方法，时间复杂度从 O(log n) 到 O(n) 不等。
方法选择取决于具体需求和应用约束。选择合适的算法对齐应用的效率和性能目标至关重要。