题解 | 求峰谷点数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求序列a中的峰、谷点的个数
     * @param a int整型一维数组 序列a
     * @return int整型
     */
    public int countPeakPoint (int[] a) {
        if(a.length<3){
            return 0;
        }

        int count = 0;// 计数器，每找到一个峰点或谷点就+1

        // 最后三个 ： a.length-3   a.length-2   a.length-1
	    // 使用三个指针 i, j, k 形成滑动窗口
        for(int i = 0,j=1,k=2;k<a.length;k++){
            // 峰点或谷点
            if((a[i]<a[j] && a[j]>a[k]) || (a[i]>a[j] && a[j]<a[k])){
                count++;
            }
		  // 滑动窗口：i, j, k 各向前移动一位
            i = j;
            j = k;
        }
        return count;
    }
}

算法特点

1. 时间复杂度：O(n)，只需遍历一次数组
2. 空间复杂度：O(1)，只用了几个变量
3. 滑动窗口：通过 i = j; j = k; 实现窗口向前滑动
4. 边界处理：自动跳过首尾元素（它们无法成为极值点）