# LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points
###### tags: `python`、`LeetCode`、`Linked List`
>這邊使用Python解題
## 題目：
A **critical point** in a linked list is defined as **either** a **local maxima** or a **local minima**.
A node is **a local maxima** if the current node has a value **strictly greater** than the previous node and the next node.
A node is **a local minima** if the current node has a value **strictly smaller** than the previous node and the next node.
Note that a node can only be a local maxima/minima if there exists **both** a previous node and a next node.
Given a linked list `head`, return *an array of length 2 containing `[minDistance, maxDistance]` where `minDistance` is the **minimum distance** between **any two distinct** critical points and `maxDistance` is the **maximum distance** between **any two distinct** critical points. If there are **fewer** than two critical points, return [-1, -1].*
### 我痛苦的翻譯:
在連結串列（Linked List）中，**關鍵點**被定義為**局部最大值**或**局部最小值**。
如果當前節點的值嚴格大於前一個節點和下一個節點的值，則該節點是**局部最大值**。
如果當前節點的值嚴格小於前一個節點和下一個節點的值，則該節點是**局部最小值**。
注意，只有當**存在前一個節點和下一個節點**時，節點才能成為局部最大值或局部最小值。
給定一個連結串列的`head`節點，返回一個長度為2的陣列`[minDistance, maxDistance]`，其中`minDistance`是任意兩個不同關鍵點之間的**最小距離**，`maxDistance`是任意兩個不同關鍵點之間的**最大距離**。如果少於兩個關鍵點，返回[-1, -1]。
## 範例
### 範例 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。
> * 最大距離是在第三個節點和第六個節點之間。maxDistance = 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 都是 5 - 2 = 3。
> * 注意，最後一個節點不被視為局部最大值，因為它沒有下一個節點。
## 條件限制
* 串列中的節點數範圍為 `[2, 10^5]`。
* `1 <= Node.val <= 10^5`
## 我的解題思路：
1. 遍歷連結串列:
* 目的：識別關鍵點，它們要麼是局部最小值，要麼是局部最大值。
* 細節：遍歷連結串列，同時維持一個指向前一個節點和當前節點的指針。這樣可以比較前一個、當前和下一個節點的值，以確定當前節點是否為關鍵點。
2. 記錄關鍵點的位置:
* 目的：儲存關鍵點的位置（索引）以便後續計算距離。
* 細節：在遍歷串列時，如果確定某個節點是關鍵點，則將其位置存儲在一個數組或列表中。
3. 計算距離：
* 目的：確定識別到的關鍵點之間的最小和最大距離。
* 細節：
* 如果識別到的關鍵點少於兩個，立即返回`[-1, -1]`。
* 否則，計算連續關鍵點之間的最小距離以及串列中第一個和最後一個關鍵點之間的最大距離。
4. 返回結果：
* 目的：以所需格式提供最終結果。
* 細節：返回包含最小和最大距離的數組。
## 程式碼:
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
# 去除開頭結尾
# 如果n比前後數值大，則n為局部最大值
# 如果n比前後數值小，則n為局部最小值
# 目標是回傳一個List，其中包含[minDistance, maxDistance]，其中minDistance 是任意兩個不同臨界點之間的最小距離，maxDistance 是任意兩個不同臨界點之間的最大距離。
# 如果臨界點少於兩個，則傳回 [-1, -1]。
if not head or not head.next or not head.next.next:
return [-1, -1]
points = []
res = []
previousVal = head.val
# 因為開頭沒有前一個值，所以跳過
head = head.next
index = 2
while head.next != None:
# check if local minma
if previousVal > head.val and head.next.val > head.val:
points.append(index)
# check if local maxma
if head.val > previousVal and head.val > head.next.val:
points.append(index)
previousVal = head.val
index += 1
head = head.next
if len(points) <= 1:
return [-1,-1]
for idx in range(len(points)):
if idx+1 < len(points):
res.append(abs(points[idx+1]-points[idx]))
else:
break
return [min(res), max(points) - min(points)]
```
## 分析程式碼
### 時間複雜度
1. 遍歷連結串列:
* 從頭節點開始遍歷連結串列，判斷是否為局部極大值或局部極小值。這個步驟需要遍歷所有節點一次，因此時間複雜度為 𝑂(𝑛)，其中 𝑛 是連結串列的節點數。
2. 計算距離：
* 在找出所有關鍵點後，計算這些點之間的距離。由於關鍵點的數量最多為 𝑛 個，這一步需要遍歷這些關鍵點一次，因此時間複雜度也是 𝑂(𝑛)。
### 空間複雜度
1. 儲存關鍵點的位置:
* 程式碼中使用了一個列表 `points` 來儲存所有關鍵點的位置。最壞情況下，連結串列中所有節點都是關鍵點，因此 points 列表的大小最多為 𝑛。
2. 儲存距離：
* 程式中還使用了一個列表 `res` 來儲存相鄰關鍵點之間的距離。這個列表的大小最多為 𝑛−1，因為最多有 𝑛−1 對相鄰關鍵點。
### 複雜度:
* 時間複雜度為 𝑂(𝑛)。
* 空間複雜度為 𝑂(𝑛)。
### 結語
今天這題雖然難度是Medium，但其實還蠻簡單的XD 實際上就是比大小然後計算距離差，大概思考一下就成想出解法了，希望這篇文章對你有幫助，感謝觀看!
Sign in with Wallet
Connect another wallet