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
        

閒聊

時間趕上 SAFE