统计数组中峰和谷的数量

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.0 MB

/*
 * 思路：
 * 使用 Java Stream API 进行流式处理，首先转换为流，再使用 skip 和 limit 函数对索引进行调整，
 * 然后用 IntStream.range 遍历并筛选出符合条件的元素。 
 */
import java.util.stream.IntStream;

public int countPeaksAndValleys(int[] nums) {
    return (int) IntStream.range(1, nums.length - 1)
        .filter(i -> nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
        .filter(i -> (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) || 
                     (nums[i] < nums[i - 1] && nums[i] < nums[i + 1]))
        .count();
}

解释

方法:

该题解利用两个指针，i 和 start，遍历数组 nums。对于每个元素，首先通过内部 while 循环跳过相邻的相同元素，从而定位到每个独特元素的开始和结束位置（start 和 i）。如果这个独特元素的最左侧和最右侧的不相等邻居满足峰或谷的条件（即都比它小或都比它大），则将其计为一个峰或谷。该算法只遍历数组一次，并且正确处理了相邻元素相等的情况。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在函数 `countHillValley` 中，如何确保在处理数组开头和结尾的元素时不会出现数组越界错误？

▷

函数中通过两个主要的检查来避免越界错误。首先，内部 `while` 循环 (`while i < n and nums[i] == v`) 确保只要 `i` 指向的位置在数组范围内，就继续遍历。其次，最关键的是，在判断是否为峰或谷时，代码中有明确的边界检查 (`if start > 0 and i < n`)，这确保在比较 `nums[start - 1]` 和 `nums[i]` 时，索引 `start - 1` 和 `i` 都是有效的，从而避免越界。

🦆

逻辑中提到如果两侧元素都大于或都小于中间的值则为峰或谷，但在代码中如何确保这一点，特别是考虑到相同元素的影响？

▷

代码通过跳过所有连续相同的元素解决了相同元素的影响。当找到一组连续相同的元素后，通过 `while` 循环将 `i` 增加到这些元素的末尾，然后检查这组元素的前一个和后一个不相同的元素。使用条件 `((nums[start - 1] < v) == (nums[i] < v))` 来判断这两个元素是否都大于或都小于中间元素的值 `v`。这样的比较直接排除了相同元素对判断的干扰，只关注两侧不同的元素与中间值的比较。

🦆

在跳过相同元素的while循环结束后，如何处理位于数组最末尾的元素，特别是当它们是连续相同的情况？

▷

当 `while` 循环结束后，`i` 可能会等于数组长度 `n`，这表示已经遍历到数组的末尾。在这种情况下，如果连续相同的元素组成的序列位于数组的最末尾，它们就不会被计为峰或谷，因为它们没有右侧的邻居元素进行比较。这种设计确保只有当连续相同的元素组既有有效的左侧也有有效的右侧邻居时，才会被考虑为峰或谷。

🦆

变量 `v` 在代码中的作用是什么，它如何帮助确定峰或谷？

▷

变量 `v` 在代码中用于记录当前正在处理的一组连续相同元素的值。这对于确定峰或谷至关重要，因为峰或谷的判断依赖于这组元素的值与其左右邻居的值的比较。通过记录 `v`，我们可以轻松地将这组元素的值与其左侧（`nums[start - 1]`）和右侧（`nums[i]`）的元素进行比较，以确定是否满足峰或谷的条件。

统计数组中峰和谷的数量

题目描述

代码结果

解释

代码细节讲解

相关问题