LeetCode解题 Day15

978. Longest Turbulent Subarray

https://leetcode.com/problems/longest-turbulent-subarray/

题目解释

请从阵列arr 找出 "turbulent" 子阵列，turbulent意思如下:

当 arr[i] 大於arr[i+1]时，arr[i+2] 也要大於arr[i+1]，简单来说就是上个数字比较大(小)，下个数字也要较大(小)

example

解法

今天有点来不及了，所以先拿别人的程序码讲解

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        
        def cmp(a, b):
            if a > b: return 1
            elif a < b: return -1
            else: return 0
        
        N = len(arr)
        ans = 1
        anchor = 0

        for i in range(1, N):
            c = cmp(arr[i-1], arr[i])
            if c == 0:
                anchor = i
            elif i == N-1 or c * cmp(arr[i], arr[i+1]) != -1:
                ans = max(ans, i - anchor + 1)
                anchor = i
        return ans

阵列中比大小会出现 >、<、= 三种状况，我们将他对应到 1、-1、0

接着我们比较前一项(arr[i-1], arr[i])，如果等於0就记录位置当作起点

接着比较後项的对应数字，并乘上前项对应数字:

如果等於-1就代表数字间的大小於有变换，也就是我们要记录的Turbulent
如果不等於-1就代表数字连续出现大於或小於，那就记录位置当作起点

解法2

9/16补上自己的想法

两个数字之间的关系就只有三种，所以我们只要记录前一组碰到的关系就好

当前一组是等於，我们就记录长度1
当前一组是大於或小於，我们就记录起始的长度2，或是长度继续加一

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        ans = 1
        sign = '>'
        
        count = 1
        for i in range(1, len(arr)):
                
            if arr[i-1] == arr[i]:
                count = 1
            
            if arr[i-1] > arr[i]:
                if sign == '>': count = 2
                else: count += 1
                    
                sign = '>'
                    
            if arr[i-1] < arr[i]:
                if sign == '<': count = 2
                else: count += 1
                    
                sign = '<'
                
            ans = max(ans, count)
        
        return ans