Given an integer array
A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
More formally, a subarray
- For
i <= k < j :arr[k] > arr[k + 1] whenk is odd, andarr[k] < arr[k + 1] whenk is even.
- Or, for
i <= k < j :arr[k] > arr[k + 1] whenk is even, andarr[k] < arr[k + 1] whenk is odd.
Example 1:
Input: arr = [9,4,2,10,7,8,8,1,9] Output: 5 Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
Example 2:
Input: arr = [4,8,12,16] Output: 2
Example 3:
Input: arr = [100] Output: 1
Constraints:
1 <= arr.length <= 4 * 104 0 <= arr[i] <= 109
Solution
這題的想法類似 DP,但可以簡化用兩個變數來處理就好
分別是 inc 和 dec,分別代表向上的長度,和向下的長度
而這題的重點在於,inc 的狀態必須從 dec 來,反之 dec 的狀態必須從 inc 來
這是為了符合題意向上之後必須向下的規定
那另外要注意的是,當用 dec 來更新 inc 的狀態後,dec 必須 reset
因為不需要紀錄之前 dec 的狀態,當下是 inc 的狀態,要找新的 dec
kotlin
沒有留言:
張貼留言