如何将寻找数组中山峰与山谷的算法优化至O(N)复杂度？

先明确一下你的需求：我们需要找出列表中所有符合条件的「山峰」或「山谷」——连续相同的数字视为一个整体，若这个整体比左右两侧邻居都大（山峰）或都小（山谷），就计数一次。你给出的例子验证了规则：比如[1,0,0,0,1]返回3，[0,1,0,1,0]返回5，[0,2,2,1,1,0,0]返回3。

首先要说明的是：这个问题的最优时间复杂度就是O(N)，因为我们必须遍历数组中的每个元素至少一次，才能确定所有连续重复块的边界和它们的大小关系，不可能做到比O(N)更优。你的原代码其实时间复杂度也是O(N)（每个元素最多被访问一次，嵌套的while只是跳过重复元素，没有重复遍历），但逻辑过于复杂，可读性差，容易在边界条件上出错。下面我给出两种更简洁、易维护的O(N)实现方案：

方案一：先压缩数组，再统计 #

思路是先把原数组压缩成一个没有连续重复元素的新数组（每个连续重复块只保留一个值），然后遍历这个压缩后的数组，统计符合条件的块：

实现代码 #

def compress(arr):
    if not arr:
        return []
    compressed = [arr[0]]
    for num in arr[1:]:
        if num != compressed[-1]:
            compressed.append(num)
    return compressed

def hill_and_valley(s):
    if len(s) <= 1:
        return 0
    compressed = compress(s)
    n = len(compressed)
    if n == 1:
        return 0  # 所有元素相同，没有山峰/山谷
    
    count = 0
    # 处理第一个块：只要和相邻块不同就计数
    if compressed[0] != compressed[1]:
        count += 1
    
    # 处理中间块：判断是否是山峰或山谷
    for i in range(1, n-1):
        prev, curr, next_val = compressed[i-1], compressed[i], compressed[i+1]
        if (curr > prev and curr > next_val) or (curr < prev and curr < next_val):
            count += 1
    
    # 处理最后一个块：只要和相邻块不同就计数
    if compressed[-1] != compressed[-2]:
        count += 1
    
    return count

测试验证 #

• 输入[1,0,0,0,1]，压缩后为[1,0,1]，计数为3，符合预期
• 输入[0,1,0,1,0]，压缩后和原数组一致，计数为5，符合预期
• 输入[0,2,2,1,1,0,0]，压缩后为[0,2,1,0]，计数为3，符合预期

方案二：直接遍历原数组，跳过重复元素 #

不需要额外创建压缩数组，直接在遍历过程中跳过连续重复的元素，跟踪当前块、前一个块和后一个块的关系：

实现代码 #

def hill_and_valley(s):
    if not s or len(s) < 2:
        return 0
    n = len(s)
    
    # 跳过第一个块的所有重复元素，找到第一个不同的位置
    i = 1
    while i < n and s[i] == s[0]:
        i += 1
    if i == n:
        return 0  # 数组所有元素相同，无山峰/山谷
    
    count = 1  # 第一个块符合条件
    prev_block = s[0]
    curr_block = s[i]
    i += 1
    
    while i < n:
        # 跳过当前块的所有重复元素
        while i < n and s[i] == curr_block:
            i += 1
        
        if i == n:
            # 最后一个块，和前一个块不同就计数
            count += 1
            break
        
        next_block = s[i]
        # 判断当前块是否是山峰或山谷
        if (curr_block > prev_block and curr_block > next_block) or (curr_block < prev_block and curr_block < next_block):
            count += 1
        
        # 更新块的指针
        prev_block = curr_block
        curr_block = next_block
        i += 1
    
    return count

复杂度分析 #

这两种方案的时间复杂度都是O(N)：

• 方案一中的压缩过程是O(N)，遍历压缩数组是O(M)（M≤N），总复杂度O(N)
• 方案二中每个元素最多被访问一次，嵌套的while循环只是跳过重复元素，没有重复遍历，总复杂度O(N)

对原代码的优化建议 #

你的原代码逻辑太绕，比如分多个分支处理首尾和中间情况，变量pre的管理容易混乱。优化的核心是把连续重复元素视为一个整体，只需要跟踪每个块的起始值，以及它前后块的大小关系，就能清晰统计符合条件的块数量。

内容的提问来源于stack exchange，提问作者12345