1

给定一个数字数组（或在本例中为 pandas 系列）返回最长的摆动子数组。摆动数组是这样一种数组，即数字在方向上交替 - 它们严格地上下波动。IE

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

Output: [49, 50, 31, 60, 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
4

1 回答 1

1

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

这是有效的，因为如果一个元素打破了条件，那么就没有更好的答案，包括该元素之前的范围和之后的范围。

我不在我的机器上运行代码，但这里有一个例子（按照评论）：

def zigzag(arr):
    mx, cur, lst, op = 0, 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, 50, 31, 60, 15]
于 2019-11-08T20:53:37.567 回答