Re: [閒聊] 每日leetcode

[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;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720140551.A.AF2.html
→ sustainer123: 大師
推 DJYOMIYAHINA: 你好細心
→ family2909: 時間兩倍是因為找點時可以順便算距離ㄅ