Day 2: LeetCode 978. Longest Turbulent Subarray

Tag:随意刷-每月挑战(2021.09.15)

Source:

978. Longest Turbulent Subarray

1.题意:

In: arr
Out: 最长turbulent subarray

符合条件1或是条件2即是turbulent.

条件1:
arr 中奇数位置(前)的值要比偶数位置(後)的值大
arr 中偶数位置(前)的值要比奇数位置(後)的值小
Or
条件2:
arr 中偶数位置(前)的值要比奇数位置(後)的值大
arr 中奇数位置(前)的值要比偶数位置(後)的值小

Note:

A subarray is a contiguous part of array.

2.思路:

图解:

作法:

• 分两个部分:
  • 第一个部分:遍历arr，检查目前所在的index，是even index还是odd index。
    • 无论是even index的话或是odd index的话，
      藉由检查符合条件1或是条件2，来设定状态.
    • 与上次(Previous)纪录状态(Status)是否相同，
      • 相同的话(或是上一状态属於初始状态): 将目前状态对应的Counter++，
        维持/切换成 目前条件的对应状态;
      • 不同的话: Reset成 初始Counter以及更新Status成 另一状态;
    • 过程即纪录最长的turbulent
  • 第二个部分:
    • 两个条件各有其存的最长turbulent(c1_max,c2_max)，取大回传(max(c1_max,c2_max))
    • 如果c1_max与c2_max相等，
      • 没有符合条件1或条件2，回传1
      • 有则择1(c1_max,c2_max)回传即可

3.程序码:

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        
        c1 = 1 
        c2 = 1 
        c1_max = (-1)
        c2_max = (-1)
        
        if len(arr)==1:
            return 1
        
        status = (-1)
        
        for i in range(len(arr)-1):
            
            print("i-Status:",i,status)
            print("c1_max:",c1_max)
            print("c2_max:",c2_max)
            # if is even
            if i%2==0:
                if arr[i]>arr[i+1]:
                    if status==2 or status==(-1): 
                        c2+=1
                        status = 2
                    else:
                        c2+=1
                        c1 = 1
                        status = (2)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2                        
                elif arr[i]<arr[i+1]:
                    if status==1 or status==(-1): 
                        c1+=1
                        status = 1
                    else:
                        c1+=1
                        c2 = 1
                        status = (1)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2                        
                else:
                    
                    # end of subarry
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2
                    c1 = 1
                    c2 = 1
                    status = (-1)
            # if is odd
            elif i%2!=0:
                if arr[i]<arr[i+1]:
                    if status==2 or status==(-1): 
                        c2+=1
                        status = 2
                    else:
                        c2+=1
                        c1 = 1
                        status = (2)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:

                        c2_max = c2                        
                elif arr[i]>arr[i+1]:
                    if status==1 or status==(-1): 
                        c1+=1
                        status = 1
                    else:
                        c1+=1                        
                        c2 = 1  
                        status = (1)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2                        
                else:
                    status = (-1)
                    if c1 > c1_max:
                        c1_max = c1
                    if c2 > c2_max:
                        c2_max = c2
                    c1 = 1
                    c2 = 1
                    
        if c1_max > c2_max:
            print("c1")
            return c1_max
        elif c1_max == c2_max and c1_max==(-1):
            print("the same")
            return 1

        else: #c2_max > c1_max or (c1_max == c2_max and c1_max!=(-1))
            print("c2")
            return c2_max

Result:

Level:Medium

相关推荐:

LeetCode 付费版在坑钱? Is LeetCode Premium Worth It in 2021?