※ 引述《smart0eddie (smart0eddie)》之铭言：
: 2024-07-05
: 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points
: 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].
: 因为是 LL 好像不能干嘛
: 只能乖乖走
: 程式会分两阶段
: 第一个部分先纪录符合条件的 node index
: 第二个部分算所有 index 之间的 min distance
: max dist 直接是 index 最后减最前
: 我应该是少做 early return
: 还有多做 function 去判断 critical point
: 时间大概是 100% 的两倍
: /**
: * 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) {
: vector<int> ans(2, -1);
: vector<int> idx;
: int i = 1;
: while (head->next && head->next->next) {
: if (isCritical(head)) {
: idx.push_back(i);
: }
: head = head->next;
: i++;
: }
: if (idx.size() >= 2) {
: ans[1] = idx.back() - idx.front();
: ans[0] = idx[1] - idx[0];
: for (int i = 2; i < idx.size(); i++) {
: if (idx[i] - idx[i-1] < ans[0]) {
: ans[0] = idx[i] - idx[i-1];
: }
: }
: }
: return ans;
: }
: private:
: bool isCritical(ListNode* node) {
: if (node->val < node->next->val && node->next->val >
: node->next->next->val) {
: return true;
: }
: if (node->val > node->next->val && node->next->val <
: node->next->next->val) {
: return true;
: }
: return false;
: }
: };
思路:
差不多
就分成两步 找区域最大值与区域最小值
找最短距离
不过应该能在找点的同时找最短距离
不过我懒得想了 姆咪
Python Code:
# 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]:
record = []
pre = head.val
head = head.next
post = 0
count = 1
while head and head.next:
post = head.next.val
if head.val > pre and head.val > post:
record.append(count)
if head.val < pre and head.val < post:
record.append(count)
pre = head.val
count += 1
head = head.next
min_distance = float('inf')
if len(record) < 2:
return [-1,-1]
for i in range(1,len(record)):
min_distance = min(record[i]-record[i-1],min_distance)
return (min_distance,record[-1]-record[0])