[LeetCode] 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

https://leetcode.com/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/description/

leetcode - Find the Minimum and Maximum Number of Nodes Between Critical Points

문제 유형 : 연결리스트, 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

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].

 

critical point는 local maxima 또는 local minima인 연결리스트의 요소이다.

local maxima는 이전과 다음의 노드들의 값들보다 엄격히 큰(같음은 포함 x)노드를 말하고,

local minima는 이전과 다음의 노드들의 값들보다 엄격히 작은 노드를 말한다.

 

연결리스트의 head가 주어진다. 두 칸 짜리 배열 [minDistance, maxDistance]를 반환하시오.

minDistance는 두 critical point의 최소 거리이고,

maxDistance는 두 ciritcal point의 최대 거리이다.

critical points가 2개 이하이면, [-1, -1]을 반환하시오.

 

풀이

포인터를 세 개 만든다. left, mid, right.

left는 이전 노드, mid는 현재 노드, right는 다음 노드를 나타낸다.

각각 0인덱스, 1인덱스, 2인덱스부터 시작한다.

만약 mid나 right이 NULL이면, [-1, -1]을 반환한다.

 

인덱스를 저장하기 위한 변수

firstCritical - 최초의 critical point의 인덱스

lastCritical - 가장 마지막에 나온 critical point의 인덱스

 

최초의 critical point를 찾는다.

만약 최초의 critical point가 연결리스트의 끝까지도 없다면, [-1, -1]을 반환한다.

 

최초의 critical point를 찾고, 이후 나머지 연결리스트를 계속 순회한다.

만약 critical point라면, minDistance = min(minDistance, 현재 인덱스 - lastCritical)로, minDistance를 갱신한다. 어차피 순차적으로 비교하므로, minDistance의 업데이트를 이렇게 선형적으로 할 수 있다.

lastCritical을 현재 인덱스로 업데이트한다.

maxDistance = lastCritical - firstCritical로 maxDistance를 업데이트한다.

만약 순회가 끝나고도 lastCritical이 firstCritical이라면, critical point가 1개란 뜻으로, [-1, -1]을 반환한다.

 

[minDistance, maxDistance]를 반환한다.

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

/**
 * 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) {
        auto left = head;
        auto mid = left -> next;
        auto right = mid -> next;

        int minimumDistance = INT_MAX;
        int maximumDistance = -1;
        int idx = 1;
        int lastCritical = 0;
        int firstCritical = 0;
        if(mid == NULL || right == NULL) return {-1, -1};

        while(firstCritical == 0 && right != NULL) {
            // islocalMaxima
            if(mid -> val > left -> val && mid -> val > right -> val) {
                firstCritical = idx;
                lastCritical = idx;
            }
            // islocalMinima
            else if(mid -> val < left -> val && mid -> val < right -> val) {
                firstCritical = idx;
                lastCritical = idx;
            }
            left = left -> next;
            mid = mid -> next;
            right = right -> next;
            idx++;
        }
        if(firstCritical == 0) return {-1, -1};
        while(right != NULL) {
            // islocalMaxima
            if(mid -> val > left -> val && mid -> val > right -> val) {
                minimumDistance = min(minimumDistance, idx - lastCritical);
                lastCritical = idx;
                maximumDistance = lastCritical - firstCritical;
            }
            // islocalMinima
            else if(mid -> val < left -> val && mid -> val < right -> val) {
                minimumDistance = min(minimumDistance, idx - lastCritical);
                lastCritical = idx;
                maximumDistance = lastCritical - firstCritical;
            }
            left = left -> next;
            mid = mid -> next;
            right = right -> next;
            idx++;
        }
        if(firstCritical == lastCritical) return {-1, -1};
        
        return {minimumDistance, maximumDistance};
    }
};