iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
自我挑戰組

每日LeetCode解題紀錄系列 第 15

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

https://i.imgur.com/QdfqdVN.png


解答

今天有點來不及了,所以先拿別人的程式碼講解

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就代表數字連續出現大於或小於,那就記錄位置當作起點

閒聊

時間趕上 SAFE


上一篇
LeetCode解題 Day14
系列文
每日LeetCode解題紀錄15

尚未有邦友留言

立即登入留言