這題的題目在這裡:
題目敘述
題目會給一個輸入陣列，裡面的數字分別代表每個index對應到的高度，要求我們計算山峰與低谷的數目，總共有多少個。
山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
測試範例
Example 1:
Input: nums = [2,4,1,1,6,5]
Output: 3
Explanation:
At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.
At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.
At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.
At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.
At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.
At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley.
There are 3 hills and valleys so we return 3.
Example 2:
Input: nums = [6,6,5,5,4,1]
Output: 0
Explanation:
At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley.
At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley.
At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley.
At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley.
At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley.
At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley.
There are 0 hills and valleys so we return 0.
約束條件
Constraints:
3 <= nums.length <= 1001 <= nums[i] <= 100
演算法
反璞歸真，我們就把自己當成登山者，左邊是登山入口，從左邊開始，沿著山陵起伏走到右邊終點。
沿途中先上坡，再下坡的地方就是hill山峰，計數器就累加一。
同理類推
沿途中先下坡，再上坡的地方就是valley低谷，計數器再累加一。
最後計數器的值就是最終答案，也是題目所求。
附註:
山峰和低谷的概念，很像我們在微積分學過的相對最大值，和相對最小值。
程式碼
class Solution:
def countHillValley(self, nums: List[int]) -> int:
INIT, UP_HILL, DOWN_HILL = 0, 1, 2
state = INIT
# counter of {hill, valley}
counter = 0
for i in range( 1, len(nums) ):
# Now we are goind up
if nums[i] > nums[i-1]:
if state == DOWN_HILL:
# previous state is DOWN_HILL, but now it is UP_HILL
# we just pass thorugh a valley
counter +=1
state = UP_HILL
# Now we are goind down
elif nums[i] < nums[i-1]:
if state == UP_HILL:
# previous state is UP_HILL, but now it is DOWN_HILL
# we just pass thorugh a hill
counter +=1
state = DOWN_HILL
return counter
複雜度分析
時間複雜度:
O( n ) 從左到右掃描一遍，每個數字拿去和前面的數字比大小。
空間複查度:
O( 1 ) 只有用到固定大小的臨時變數，占用的記憶體空間為常數級別O(1)。
關鍵知識點
這題算是前面那題單調數列的延伸題，從遞增、遞減的變化，
去找出山峰、低谷對應的變化規律分別是 先遞增再遞減、先遞減再遞增。
可以複習相關的題目，去鞏固知識點(找最小值、最大值、和遞增遞減的變化)。
Reference:
[1] Python O(n) by simulation [w/ Visualiztion] - Count Hills and Valleys in an Array - LeetCode
