【DP】978. Longest Turbulent Subarray

题目描述：

A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16]
Output: 2

Example 3:

Input: [100]
Output: 1

Note:

1 <= A.length <= 40000
0 <= A[i] <= 10^9

解题思路：

求最长湍流子数组，在这个子数组中，相邻数值交替大小，如 [4 3 2 6 5]，就好像波浪一样，故为“湍流”。

很容易想到动态规划的方法，dp[i] 记录数组中 i 位置的湍流长度。最后 max(dp) 就是最终的答案。

转移方程式也比较容易观察出来：

对于 i 位置的数字，如果满足湍流条件 (A[i-1] > A[i-2] and A[i-1] > A[i]) or (A[i-1] < A[i-2] and A[i-1] < A[i])，则 dp[i] = dp[i-1] + 1；
不满足湍流条件时，如果 A[i] == A[i-1]，说明当前数字与前一个数字相同，dp[i] = 1；如果当前数字与前一个数字不相同，dp[i] = 2。

如 A = [9,4,2,10,7,8,8,1,9]，只需要遍历一遍，dp 就会得到 [1,2,2,3,4,5,1,2,3]，max(dp) = 5 就是最后的答案。

时间复杂度和空间复杂度均为 O(n)。

Python3 实现：

class Solution(object):
    def maxTurbulenceSize(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        lens = len(A)
        if lens == 1:
            return 1
        dp = [0] * lens
        dp[0] = 1
        dp[1] = 1 if A[0] == A[1] else 2  # 所有数字都相同
        for i in range(2, lens):
            if (A[i-1] > A[i-2] and A[i-1] > A[i]) or (A[i-1] < A[i-2] and A[i-1] < A[i]):
                dp[i] = dp[i-1] + 1
            elif A[i] == A[i-1]:  # 与前一个数字相同，初始值为1
                dp[i] = 1
            elif A[i] != A[i-1]:  # 与前一个数字不相同，初始值为2
                dp[i] = 2
        return max(dp)

print(Solution().maxTurbulenceSize([9,4,2,10,7,8,8,1,9]))  # 5 ([4,2,10,7,8])
print(Solution().maxTurbulenceSize([4,8,12,16]))  # 2 ([4,8])
print(Solution().maxTurbulenceSize([4,4,4]))  # 1 ([4])

最后编辑于：2019.05.10 09:54:11