0978._Longest_Turbulent_Subarray.md

978. Longest Turbulent Subarray

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

Sliding window, we only care about the comparisons between adjacent elements. If the comparisons are represented by 0, 2, 1 (for <, =, >), I use a filps(list) to represent this.

class Solution:
    def maxTurbulenceSize(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if not A:
            return 0
        if len(A) <= 1:
            return len(A)
        
        flips = [0]
        for i in range(1, len(A)):
            if A[i] > A[i-1]:
                flips.append(1)
            elif A[i] == A[i-1]:
                flips.append(2)
            else:
                flips.append(0)
                
        idx = 1
        while idx < len(flips) and flips[idx] == 2:
            idx += 1
        if idx == len(flips):
            return 1
        flips[idx-1] = 0 if flips[idx] == 1 else 1
        
        s = start = idx
        res, prev = 1, flips[idx-1]
        while start < len(flips):
            cur = flips[start]
            if cur == 1 - prev or prev == 2:
                if prev == 2:
                    s += 1
            else:
                res = max(res, start - s + 1)
                s = start
            start += 1
            prev = cur
            
        res = max(res, start - s + 1)
        return res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

参考solution

因为python3 里面没有cmp函数了，所以自己实现了

class Solution(object):
    def maxTurbulenceSize(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        def cmp(a, b): # -1, 0, 1 for (a < b, a = b, a > b)
            return (a > b) - (a < b)
        
        res, anchor = 1, 0
        for i in range(1, len(A)):
            c = cmp(A[i-1], A[i])
            if i == len(A) - 1 or c * cmp(A[i], A[i+1]) != -1:
                res = max(res, i - anchor + 1)
                anchor = i
        return res