🔗 🟡 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points 1311

tags: `Weekly Contest 265` `鏈結串列(Linked List)`

題意

在鏈結串列(Linked List) 中， 臨界點(critical point) 被定義為 局部最大值(local maxima) 或 局部最小值(local minima) 。

如果當前節點的值嚴格大於前一個節點和下一個節點，則該節點是 局部最大值(local maxima) 。
如果當前節點的值嚴格小於前一個節點和下一個節點，則該節點是 局部最小值(local minima) 。
但需要注意的是，一個節點只有在存在前一個節點和下一個節點的情況下，才可能是 局部最大值/最小值 。

給定一個鏈結串列(Linked List) 的頭節點 $\text{head}$ ，返回一個長度為2的陣列 $[\text{minDistance}, \text{maxDistance}]$ ，其中 $\text{minDistance}$ 是任意兩個不同臨界點之間的最小距離， $\text{maxDistance}$ 是任意兩個不同臨界點之間的最大距離。如果臨界點少於2個，則返回 $[-1, -1]$ 。

思路：維護第一個和最後一個臨界點的索引

根據題意，我們需要計算臨界點之間的 $\text{minDistance}$ 和 $mn = \text{maxDistance}$ 。而 $\text{maxDistance}$ 就是第一個和最後一個臨界點之間的距離；而 $\text{minDistance}$ 則是任意兩個不同臨界點之間距離的最小距離。因此，我們只需要維護第一個臨界點的索引 $\text{first}$ 和最後一個臨界點的索引 $\text{last}$ 即可。

令 $idx$ 表示當前節點的索引、 $pre$ 和 $cur$ 分別指向前一個節點和當前節點。初始化 $\text{first}$ 和 $\text{last}$ 為 $-1$ ， $mn$ 為正無窮大。遍歷鏈結串列，若當前節點為臨界點：

如果是第一個臨界點，更新 $first$ 為當前索引。
否則更新 $mn = \min(mn, \text{idx} - \text{last})$ 。
然後更新 $last$ 為當前索引。

遍歷結束後，若找到了至少兩個臨界點，則返回 $[\text{mn}, \text{last} - \text{first}]$ ；否則返回 $[-1, -1]$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 為鏈結串列的長度。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        pre, cur = None, head
        first = last = -1
        mn = float('inf') # min distance
        idx = 0
        while cur and cur.next:
            if pre is not None and (pre.val < cur.val > cur.next.val or pre.val > cur.val < cur.next.val):
                if first == -1:
                    first = idx
                else:
                    mn = min(mn, idx - last)
                last = idx
            pre, cur = cur, cur.next
            idx += 1
        return [mn, last - first] if mn != float('inf') else [-1, -1]

class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        ListNode *pre = nullptr, *cur = head;
        int first = -1, last = -1;
        int mn = INT_MAX; // min distance
        int idx = 0;
        while (cur && cur->next) {
            if (pre != nullptr && (pre->val < cur->val && cur->val > cur->next->val || pre->val > cur->val && cur->val < cur->next->val)) {
                if (first == -1) first = idx;
                else mn = min(mn, idx - last);
                last = idx;
            }
            pre = cur;
            cur = cur->next;
            idx++;
        }
        return mn != INT_MAX ? vector<int>{mn, last - first} : vector<int>{-1, -1};
    }
};