找出峰值
难度:
标签:
题目描述
You are given a 0-indexed array mountain. Your task is to find all the peaks in the mountain array.
Return an array that consists of indices of peaks in the given array in any order.
Notes:
- A peak is defined as an element that is strictly greater than its neighboring elements.
- The first and last elements of the array are not a peak.
Example 1:
Input: mountain = [2,4,4] Output: [] Explanation: mountain[0] and mountain[2] can not be a peak because they are first and last elements of the array. mountain[1] also can not be a peak because it is not strictly greater than mountain[2]. So the answer is [].
Example 2:
Input: mountain = [1,4,3,8,5] Output: [1,3] Explanation: mountain[0] and mountain[4] can not be a peak because they are first and last elements of the array. mountain[2] also can not be a peak because it is not strictly greater than mountain[3] and mountain[1]. But mountain [1] and mountain[3] are strictly greater than their neighboring elements. So the answer is [1,3].
Constraints:
3 <= mountain.length <= 1001 <= mountain[i] <= 100
代码结果
运行时间: 23 ms, 内存: 16.0 MB
/*
题目思路：
使用Java Stream，我们可以利用IntStream.range创建索引流，然后对索引流进行过滤，保留那些严格大于其相邻元素的索引。
*/
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class FindPeaksStream {
public static List<Integer> findPeakIndices(int[] mountain) {
return IntStream.range(1, mountain.length - 1)
.filter(i -> mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1])
.boxed()
.collect(Collectors.toList());
}
public static void main(String[] args) {
int[] mountain = {1, 4, 3, 8, 5};
System.out.println(findPeakIndices(mountain)); // 输出：[1, 3]
}
}
解释
方法:
此题解的思路是遍历数组mountain，从第二个元素到倒数第二个元素（因为第一个和最后一个元素不可能是峰值）。对于每个元素，检查它是否严格大于它的左右相邻元素。如果是，那么这个元素就是一个峰值，将其下标添加到结果列表中。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么我们在寻找峰值时只能排除数组的第一个和最后一个元素？这是否意味着在某些特定的数组结构中，我们可能会错过边界峰值？
▷🦆
在题解中提到，如果`mountain[i]`严格大于其左右相邻元素，则认为它是峰值。这种方法是否能处理所有连续重复元素的情况，比如`[1, 2, 2, 3, 2]`这样的数组？
▷🦆
如果数组`mountain`的元素全部相同，比如`[5, 5, 5, 5]`，题解的逻辑是否还能正确判断没有峰值？
▷