題目連結:
題目意譯:
一個連結串列(Linked List)的臨界點定義為一個局部最大值或是局部最小值。
一節點如果其值嚴格大於前一個節點以及後一個節點的話,則為局部最大值。
一節點如果其值嚴格小於前一個節點以及後一個節點的話,則為局部最小值。
注意,一節點如果存在前一個以及後一個節點的話才可能為局部最大值或局部最小值。
給定一連結串列開頭 head,回傳一個長度為 2 的陣列其包含著 [minDistance, maxDistance],其中 minDistance 為兩個相異臨界點的最小距離,而 maxDistance 為兩個相異臨界點的最大距離。如果串列中少於兩個臨界點,則回傳 [-1, -1]。
限制:
串列中的節點數位於範圍 [2, 10 ^ 5] 中。
1 ≦ Node.val ≦ 10 ^ 5
範例測資:
範例 1:
輸入: head = [3,1]
輸出: [-1,-1]
解釋: [3,1] 中沒有臨界點。
範例 2:
輸入: head = [5,3,1,2,5,1,2]
輸出: [1,3]
解釋: 有三個臨界點:
- [5,3,1,2,5,1,2]: 第三個節點為一個局部最小值,因為 1 小於 3 以及 2。
- [5,3,1,2,5,1,2]: 第五個節點為一個局部最大值,因為 5 大於 2 以及 1。
- [5,3,1,2,5,1,2]: 第六個節點為一個局部最小值,因為 1 小於 5 以及 2。
最大距離發生於第五與第六個節點之間。minDistance = 6 - 5 = 1。
最小距離發生於第三與第六個節點之間。minDistance = 6 - 3 = 3。
範例 3:
輸入: head = [1,3,2,2,3,2,2,2,7]
輸出: [3,3]
解釋: 有兩個臨界點:
- [1,3,2,2,3,2,2,2,7]: 第二個節點為一個局部最小值,因為 3 小於 1 以及 2。
- [1,3,2,2,3,2,2,2,7]: 第五個節點為一個局部最大值,因為 3 大於 2 以及 2。
最小以及最大距離發生於第二與第五個節點之間。
因此 minDistance 和 maxDistance 為 6 - 5 = 1。
注意,最後一個節點不算作局部最大值因為它沒有下一個節點。
解題思維:
就是單純地先掃過一次串列,然後根據題目的定義把所有臨界點找出來以及它們各自距離 head 有多遠。
如果臨界點少於 2 個,則直接回傳 [-1, -1] 即可;反之,依序掃過所有臨界點並把兩兩相鄰的求出距離,便可以找出相距最小值,而第一個和最後一個臨界點的距離即為最大值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。