一魚多吃 用比大小的技巧 計算高峰與低谷的數目 Count Hills and Valleys in an Array

這題的題目在這裡:

題目敘述

題目會給一個輸入陣列，裡面的數字分別代表每個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 <= 100
• 1 <= 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