返回最长摆动子数组

2024-05-20 • 问答

给出一个数字数组（或本例中的pandas系列）返回最长的摆动子数组。摆动数组是一种使得数字在方向上交替的数组-它们严格地上下移动。即

Input: [10,22,9,33,49,50,31,60,15]

Output: [49,15]

必须按顺序形成数组，即您不能通过跳过值来形成数组。

我的朴素暴力方法可以在下面找到-我很难使它起作用。有提示吗？

def zigzag(arr):
    result = pd.Series([])
    for i in range(len(arr)-2):
         if arr[i:i+3] != sorted(arr[i:i+3]) and arr[i:i+3] != sorted(arr[i:i+3],reverse = True): # no three points increase or decrease
            result = result.append(pd.Series(arr[i:i+3],index = list(range(i,i+3))))
            result = result.loc[~result.index.duplicated(keep='first')] 
         else:
            result = pd.Series([])
    return result

您可以通过迭代并检查 zigzag 条件来实现具有线性复杂性的贪婪解决方案，贪婪地获取元素，直到达到破坏条件的元素，然后最大化答案（范围为已经具有不破坏条件的条件），并从当前元素（破坏条件的元素）开始重复操作。

之所以起作用，是因为如果一个元素破坏了条件，那么没有更好的答案，包括该元素之前的范围和该元素之后的范围。

我不在机器上运行代码，但这是一个示例（遵循注释）：

def zigzag(arr):
    mx,cur,lst,op = 0,-1,0
    st,en = 0,0
    ans = 0
    for i,x in enumerate(arr):
        # if its the first element we take it greedily
        if lst == -1:
            lst = x
            st = i
        # else if lst is the first element taken then decide which direction we need next
        elif op == 0:
            if x > lst:
                op = 1
            elif x < lst:
                op = -1
            # if current element is equal to last taken element we stop and start counting from this element
            else:
                # check if current range is better than previously taken one
                if i-st > mx:
                    mx = i-st
                    ans = st
                    en = i
                st = i
                op = 0

            lst = x
        else:
            # if direction meets the inequality take the current element
            if (op == 1 and x < lst) or (op == -1 and x > lst):
                op *= -1
                lst = x
            # otherwise,check if the current range is better than the previously taken one
            else:
                if i-st > mx:
                    mx = i-st
                    ans = st
                    en = i
                st = i
                lst = x
                op = 0
    # if starting index is greater than or equal to the last,then we have reached the end without checking for maximum range
    if st >= en:
        if len(arr)-st > en-ans:
            ans = st
            en = len(arr)
    result = [arr[i] for i in range(ans,en)]
    return result

print(zigzag([10,22,9,33,49,50,31,60,15]))
# [49,15]

返回最长摆动子数组

yyaiwdk1 回答：返回最长摆动子数组

大家都在问