文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

鏈表中的 臨界點(diǎn) 定義為一個(gè) 局部極大值點(diǎn) 或 局部極小值點(diǎn) 。

如果當(dāng)前節(jié)點(diǎn)的值 嚴(yán)格大于 前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是一個(gè) 局部極大值點(diǎn) 。

如果當(dāng)前節(jié)點(diǎn)的值 嚴(yán)格小于 前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是一個(gè) 局部極小值點(diǎn) 。

注意：節(jié)點(diǎn)只有在同時(shí)存在前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的情況下，才能成為一個(gè) 局部極大值點(diǎn) / 極小值點(diǎn) 。

給你一個(gè)鏈表 head ，返回一個(gè)長(zhǎng)度為 2 的數(shù)組 [minDistance, maxDistance] ，其中 minDistance 是任意兩個(gè)不同臨界點(diǎn)之間的最小距離，maxDistance 是任意兩個(gè)不同臨界點(diǎn)之間的最大距離。
如果臨界點(diǎn)少于兩個(gè)，則返回 [-1，-1] 。

示例 1：

輸入：head = [3,1] 輸出：[-1,-1] 解釋：鏈表 [3,1] 中不存在臨界點(diǎn)。

示例 2：

輸入：head = [5,3,1,2,5,1,2] 輸出：[1,3] 解釋：存在三個(gè)臨界點(diǎn)： - [5,3,1,2,5,1,2]：第三個(gè)節(jié)點(diǎn)是一個(gè)局部極小值點(diǎn)，因?yàn)?1 比 3 和 2 小。 - [5,3,1,2,5,1,2]：第五個(gè)節(jié)點(diǎn)是一個(gè)局部極大值點(diǎn)，因?yàn)?5 比 2 和 1 大。 - [5,3,1,2,5,1,2]：第六個(gè)節(jié)點(diǎn)是一個(gè)局部極小值點(diǎn)，因?yàn)?1 比 5 和 2 小。 第五個(gè)節(jié)點(diǎn)和第六個(gè)節(jié)點(diǎn)之間距離最小。minDistance = 6 - 5 = 1 。 第三個(gè)節(jié)點(diǎn)和第六個(gè)節(jié)點(diǎn)之間距離最大。maxDistance = 6 - 3 = 3 。

示例 3：

輸入：head = [1,3,2,2,3,2,2,2,7] 輸出：[3,3] 解釋：存在兩個(gè)臨界點(diǎn)： - [1,3,2,2,3,2,2,2,7]：第二個(gè)節(jié)點(diǎn)是一個(gè)局部極大值點(diǎn)，因?yàn)?3 比 1 和 2 大。 - [1,3,2,2,3,2,2,2,7]：第五個(gè)節(jié)點(diǎn)是一個(gè)局部極大值點(diǎn)，因?yàn)?3 比 2 和 2 大。 最小和最大距離都存在于第二個(gè)節(jié)點(diǎn)和第五個(gè)節(jié)點(diǎn)之間。 因此，minDistance 和 maxDistance 是 5 - 2 = 3 。 注意，最后一個(gè)節(jié)點(diǎn)不算一個(gè)局部極大值點(diǎn)，因?yàn)樗缶蜎](méi)有節(jié)點(diǎn)了。

示例 4：

輸入：head = [2,3,3,2] 輸出：[-1,-1] 解釋：鏈表 [2,3,3,2] 中不存在臨界點(diǎn)。提示： 鏈表中節(jié)點(diǎn)的數(shù)量在范圍 [2, 10^5] 內(nèi) 1 <= Node.val <= 10^5

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 鏈表遍歷

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:vector<int> nodesBetweenCriticalPoints(ListNode* head) {ListNode *prev = NULL, *cur = head, *next = head->next;int first = -1, ct = 0, prevpos = -1, curpos = -1, mindis = INT_MAX;while(cur){ct++;next = cur->next;if(prev && cur->next && ((prev->val > cur->val && next->val > cur->val)|| (prev->val < cur->val && next->val < cur->val))){curpos = ct;if(first == -1)first = ct;if(prevpos != -1)mindis = min(mindis, curpos-prevpos);prevpos = curpos;}prev = cur;cur = cur->next;}if(mindis == INT_MAX) return {-1, -1};return {mindis, curpos-first};} };

180 ms 110.6 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 2058. 找出临界点之间的最小和最大距离（链表）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。