推 JIWP: 別卷了 07/05 10:56
推 smart0eddie: 應該是可以 這樣只要記3個index 07/05 11:37
→ smart0eddie: 可是感覺很麻煩 07/05 11:37
→ sustainer123: 我有試一下 試不出來就果斷放棄 07/05 11:42
※ 引述《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])
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720148118.A.C2A.html