python - 在列表中找到所有的山丘和山谷

Question

我正在编写一个函数来查找给定列表中的所有山丘和山谷。例如，[1,0,0,0,1] 返回 3，[0,1,0,1,0] 返回 5。[0,2,2,1,1,0,0] 返回 3。如果一个数字(或具有相同值的连续数字)大于或小于它的两个邻居，它被认为是一座山或一座山谷。

下面是我的代码:

def hill_and_vally(s):
    if not s or len(s) < 2:
        return 0
    i = 0
    count = 0
    pre = None
    while i < len(s):
        if i == 0:
            while s[i] == s[i+1]:  # loop until value is different
                i += 1
            i += 1
            if i < len(s):       # check if it reaches the end 
                count += 1
                pre = s[i-1]     # track the previous value
        elif i == len(s) - 1:
            while s[i] == s[i-1]:  
                i -= 1
            i -= 1
            if i >= 0:
                count += 1
            break
        else:
            while s[i] == s[i+1]:
                i += 1
            i += 1
            if s[i] > s[i-1] and pre > s[i-1]:  # it is a valley
                count += 1
            elif s[i] < s[i-1] and pre < s[i-1]:  # it is a hill
                count += 1
            pre = s[i-1]
    return count

谁能帮我把复杂度提高到 O(N)。或者告诉我另一种更复杂的方法？请给我一些例子。提前致谢。

Answer 1

这是我的做法:

• 计算连续元素之间的差异 d(从结果中删除 0)
• 计算符号在 d 中变化的次数
• 返回 2 加上那个计数(因为即使在单调递增序列中也有山丘和山谷)

在代码中:

def hill_and_vally(s):
    d=[x1-x0 for x0,x1 in zip(s,s[1:]) if x1!=x0]
    return 2+sum(d0*d1<0 for d0,d1 in zip(d,d[1:]))

当然它可以用 for 循环和索引来实现，但是 zip 和列表理解更像 pythonic。

zip(s,s[1:]) 是获取列表中相邻元素对的常用方法。

测试:

>>> hill_and_vally([1,0,0,0,1])
3
>>> hill_and_vally([0,1,0,1,0])
5
>>> hill_and_vally([0,2,2,1,1,0,0])
3

处理极端情况，例如报告的 [1,1,1,1] 留作练习 :-)